{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #最小覆盖子串"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #hash-table #string #sliding-window"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #哈希表 #字符串 #滑动窗口"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: minWindow"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #最小覆盖子串"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给定两个字符串 <code>s</code> 和&nbsp;<code>t</code> 。返回 <code>s</code> 中包含&nbsp;<code>t</code>&nbsp;的所有字符的最短子字符串。如果 <code>s</code> 中不存在符合条件的子字符串，则返回空字符串 <code>&quot;&quot;</code> 。</p>\n",
    "\n",
    "<p>如果 <code>s</code> 中存在多个符合条件的子字符串，返回任意一个。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>注意： </strong>对于 <code>t</code> 中重复字符，我们寻找的子字符串中该字符数量必须不少于 <code>t</code> 中该字符数量。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>s = &quot;ADOBECODEBANC&quot;, t = &quot;ABC&quot;\n",
    "<strong>输出：</strong>&quot;BANC&quot; \n",
    "<strong>解释：</strong>最短子字符串 &quot;BANC&quot; 包含了字符串 t 的所有字符 &#39;A&#39;、&#39;B&#39;、&#39;C&#39;</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>s = &quot;a&quot;, t = &quot;a&quot;\n",
    "<strong>输出：</strong>&quot;a&quot;\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>s = &quot;a&quot;, t = &quot;aa&quot;\n",
    "<strong>输出：</strong>&quot;&quot;\n",
    "<strong>解释：</strong>t 中两个字符 &#39;a&#39; 均应包含在 s 的子串中，因此没有符合条件的子字符串，返回空字符串。</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= s.length, t.length &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li><code>s</code> 和 <code>t</code> 由英文字母组成</li>\n",
    "</ul>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>进阶：</strong>你能设计一个在 <code>o(n)</code> 时间内解决此问题的算法吗？</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><meta charset=\"UTF-8\" />注意：本题与主站 76&nbsp;题相似（本题答案不唯一）：<a href=\"https://leetcode-cn.com/problems/minimum-window-substring/\">https://leetcode-cn.com/problems/minimum-window-substring/</a></p>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [M1oyTv](https://leetcode.cn/problems/M1oyTv/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [M1oyTv](https://leetcode.cn/problems/M1oyTv/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['\"ADOBECODEBANC\"\\n\"ABC\"', '\"a\"\\n\"a\"', '\"a\"\\n\"aa\"']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minWindow(self, s: str, t: str) -> str:\n",
    "        \n",
    "        if len(t) > len(s):\n",
    "            return ''        \n",
    "        \n",
    "        cnt = collections.Counter(t)    # 哈希表：记录需要匹配到的各个元素的数目\n",
    "        need = len(t)                   # 记录需要匹配到的字符总数【need=0表示匹配到了】\n",
    "        \n",
    "        n = len(s)\n",
    "        start, end = 0, -1          # 记录目标子串s[start, end]的起始和结尾\n",
    "        min_len = n + 1             # 符合题意的最短子串长度【初始化为一个不可能的较大值】\n",
    "        left = right = 0            # 滑动窗口的左右边界\n",
    "        \n",
    "        for right in range(n):\n",
    "            \n",
    "            # 窗口右边界右移一位\n",
    "            ch = s[right]               # 窗口中新加入的字符\n",
    "            if ch in cnt:               # 新加入的字符位于t中\n",
    "                if cnt[ch] > 0:         # 对当前字符ch还有需求\n",
    "                    need -= 1           # 此时新加入窗口中的ch对need有影响\n",
    "                cnt[ch] -= 1\n",
    "            \n",
    "            # 窗口左边界持续右移\n",
    "            while need == 0:            # need=0，当前窗口完全覆盖了t\n",
    "                if right - left + 1 < min_len:      # 出现了更短的子串\n",
    "                    min_len = right - left + 1\n",
    "                    start, end = left, right\n",
    "                \n",
    "                ch = s[left]            # 窗口中要滑出的字符\n",
    "                if ch in cnt:           # 刚滑出的字符位于t中\n",
    "                    if cnt[ch] >= 0:    # 对当前字符ch还有需求，或刚好无需求(其实此时只有=0的情况)\n",
    "                        need += 1       # 此时滑出窗口的ch会对need有影响\n",
    "                    cnt[ch] += 1\n",
    "                left += 1               # 窗口左边界+1\n",
    "        \n",
    "        return s[start: end+1]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import collections\n",
    "class Solution:\n",
    "    def minWindow(self, s: str, t: str) -> str:\n",
    "        if len(t) > len(s):\n",
    "            return \"\"\n",
    "        #\n",
    "        hash_map = collections.Counter(t)#t.co{k:1 for k in t}\n",
    "        need = len(t)\n",
    "        len_min = len(s)+2#给个不可能的大小\n",
    "        left,rigth = 0,0\n",
    "        res = \"\"\n",
    "\n",
    "        for i in range(len(s)):\n",
    "            rigth +=1\n",
    "            if s[i] in hash_map.keys():\n",
    "                if hash_map[s[i]]>0:\n",
    "                    need -=1\n",
    "                hash_map[s[i]]-=1\n",
    "                \n",
    "            \n",
    "            while need ==0:#持续右移\n",
    "                # print(s[left:rigth],'-',need,hash_map)\n",
    "                if len_min > rigth-left:\n",
    "                    res = s[left:rigth]\n",
    "                    # print(\"res-!\",res,len_min)\n",
    "                    len_min = rigth-left \n",
    "                if s[left] in hash_map.keys():\n",
    "                    # print(\"s[left]\",s[left])\n",
    "                    hash_map[s[left]] +=1\n",
    "                    if hash_map[s[left]]>0:\n",
    "                        need +=1\n",
    "                # print(\"res-\",res)\n",
    "                left +=1#\n",
    "        \n",
    "        return res\n",
    "\n",
    "\n",
    "\n",
    "            \n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minWindow(self, s: str, t: str) -> str:\n",
    "        \"\"\"\n",
    "        典型的双指针应用\n",
    "        \"\"\"\n",
    "        if len(s) < len(t):\n",
    "            return ''\n",
    "        \n",
    "        cnt = collections.Counter(t)\n",
    "        unsat = set(cnt.keys())\n",
    "\n",
    "        n = len(s)\n",
    "        mlen = n + 1\n",
    "        mi, mj = 0, 0\n",
    "\n",
    "        i, j = 0, 0\n",
    "        while j < n:\n",
    "            if s[j] in cnt:\n",
    "                cnt[s[j]] -= 1\n",
    "                if cnt[s[j]] <= 0:\n",
    "                    unsat.discard(s[j])\n",
    "                        \n",
    "            j += 1\n",
    "\n",
    "            while len(unsat) == 0 and i < j:\n",
    "                if (t := j - i) < mlen:\n",
    "                    mlen = t\n",
    "                    mi, mj = i, j\n",
    "                if s[i] in cnt:\n",
    "                    cnt[s[i]] += 1\n",
    "                    if cnt[s[i]] > 0:\n",
    "                        unsat.add(s[i])\n",
    "                i += 1\n",
    "\n",
    "        if mlen == n + 1:\n",
    "            return ''\n",
    "        else:\n",
    "            return s[mi:mj]\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minWindow(self, s: str, t: str) -> str:\n",
    "        arr1 = [0]*50\n",
    "\n",
    "        for i in range(len(t)):\n",
    "            arr1[ord(t[i])-ord('a')] += 1\n",
    "\n",
    "        \n",
    "        if len(s)<len(t):\n",
    "            return \"\"\n",
    "        \n",
    "        left = 0\n",
    "        right = 0\n",
    "        minlen = 99999999\n",
    "        needcount = len(t)\n",
    "        index = (0,999999999999999)\n",
    "        while right<len(s):\n",
    "            if arr1[ord(s[right])-ord('a')] > 0:\n",
    "                needcount -= 1\n",
    "            arr1[ord(s[right])-ord('a')] -= 1\n",
    "            if needcount == 0:\n",
    "                while True:\n",
    "                    if arr1[ord(s[left])-ord('a')] == 0: \n",
    "                        break\n",
    "                    arr1[ord(s[left])-ord('a')] += 1\n",
    "                    left += 1\n",
    "\n",
    "                if right-left < minlen:\n",
    "                    index = (left,right)\n",
    "                    minlen = min(minlen,right-left)\n",
    "                arr1[ord(s[left])-ord('a')] += 1\n",
    "                needcount += 1\n",
    "                left += 1\n",
    "            right += 1\n",
    "        return '' if index[1]>len(s) else s[index[0]:index[1]+1]\n",
    "\n",
    "                    \n",
    "            \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minWindow(self, s: str, t: str) -> str:\n",
    "        if len(s) < len(t):\n",
    "            return \"\"\n",
    "        \n",
    "        t_d = {}\n",
    "        for ti in t:\n",
    "            t_d[ti] = t_d.get(ti, 0) + 1\n",
    "        \n",
    "        max_d = copy.copy(t_d)\n",
    "        diff_count = len(t)\n",
    "        min_str = s * 2\n",
    "        last_index = 0\n",
    "        index = 0\n",
    "        while index < len(s):\n",
    "            si = s[index]\n",
    "            if si in t_d:\n",
    "                t_d[si] -= 1\n",
    "                if t_d[si] >= 0:\n",
    "                    diff_count -= 1\n",
    "                # 刚好有一段\n",
    "                while diff_count == 0:\n",
    "                    if index - last_index + 1 < len(min_str):\n",
    "                        min_str = s[last_index: index + 1]\n",
    "                    sj = s[last_index]\n",
    "                    if sj in t_d:\n",
    "                        t_d[sj] += 1\n",
    "                        if t_d[sj] > 0:\n",
    "                            diff_count += 1\n",
    "                    last_index += 1\n",
    "                # print(s[last_index: index + 1], diff_count)\n",
    "            index += 1\n",
    "        return min_str if len(min_str) < len(s) * 2 else \"\"\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minWindow(self, s: str, t: str) -> str:\n",
    "        # sliding window\n",
    "        sLen = len(s)\n",
    "        tLen = len(t)\n",
    "        if sLen<tLen or sLen==0 or tLen==0:\n",
    "            return \"\"\n",
    "        s_as = [0]*sLen\n",
    "        t_as = [0]*tLen\n",
    "        # convert s and t to ascii\n",
    "        for i in range(sLen):\n",
    "            s_as[i] = ord(s[i])\n",
    "        for j in range(tLen):\n",
    "            t_as[j] = ord(t[j])\n",
    "\n",
    "        # 频数数组frequence array\n",
    "        # ascii('z') = 122\n",
    "        winFreq = [0]*128\n",
    "        tFreq = [0]*128\n",
    "        for i in range(tLen):\n",
    "            tFreq[t_as[i]] += 1\n",
    "\n",
    "        #distance: 滑动窗口内部包含多少t中的字符\n",
    "        distance = 0\n",
    "        minLen = sLen +1\n",
    "        begin = 0\n",
    "\n",
    "        left = 0\n",
    "        right = 0 # (left,right]\n",
    "        # right++: until contain all t\n",
    "        # then, left ++: until do not contain all t\n",
    "        # right 到数组右边界 停止\n",
    "\n",
    "        while right < sLen:\n",
    "            if tFreq[s_as[right]] == 0: #right not in t\n",
    "                right += 1\n",
    "                continue\n",
    "\n",
    "            # right in t, and this char fre < in t fre      distance ++\n",
    "            if winFreq[s_as[right]]<tFreq[s_as[right]]:\n",
    "                distance += 1\n",
    "            \n",
    "            # right in t, winFre ++\n",
    "            winFreq[s_as[right]] += 1\n",
    "            right += 1\n",
    "\n",
    "            while distance == tLen:\n",
    "                if right - left < minLen:\n",
    "                    minLen = right - left\n",
    "                    begin = left\n",
    "\n",
    "                if tFreq[s_as[left]] == 0: #left not in t\n",
    "                    left += 1\n",
    "                    continue\n",
    "                # left in t, and this char fre < in t fre distance ++\n",
    "                if winFreq[s_as[left]]==tFreq[s_as[left]]:\n",
    "                    distance -= 1\n",
    "\n",
    "                winFreq[s_as[left]] -=1\n",
    "                left += 1\n",
    "        if minLen == sLen+1:\n",
    "            return \"\"\n",
    "        return s[begin:begin+minLen]\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict\n",
    "\n",
    "class Solution:\n",
    "    def minWindow(self, s: str, t: str) -> str:\n",
    "        res = [0, len(s) + 1]\n",
    "\n",
    "        window = defaultdict(lambda : 0)\n",
    "        need_len = len(t)\n",
    "\n",
    "        for c in t:\n",
    "            window[c] += 1\n",
    "\n",
    "        cur = []\n",
    "        left = 0\n",
    "        for index, c in enumerate(list(s)):\n",
    "            if c in t:\n",
    "                if window[c] > 0:\n",
    "                    need_len -= 1\n",
    "                window[c] -= 1\n",
    "\n",
    "            while need_len <= 0 and left <= index:\n",
    "                if index - left < res[1] - res[0]:\n",
    "                    res = [left, index]\n",
    "\n",
    "                if s[left] in window:\n",
    "                    if window[s[left]] >= 0:\n",
    "                        need_len += 1\n",
    "                    window[s[left]] += 1\n",
    "                left += 1\n",
    "\n",
    "        # print(res, len(s), res[1]+1, s[12])\n",
    "        if res == [0, len(s) + 1]:\n",
    "            return \"\"\n",
    "        else:\n",
    "            return s[res[0]: res[1]+1]\n",
    "\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minWindow(self, s: str, t: str) -> str:\n",
    "        window = defaultdict(int)\n",
    "        need = defaultdict(int)\n",
    "\n",
    "        for i in t:\n",
    "            need[i] += 1\n",
    "\n",
    "        left, right = 0, 0\n",
    "        valid = 0\n",
    "        start, length = 0, float('inf')\n",
    "\n",
    "        while right < len(s):\n",
    "            c = s[right]\n",
    "            if c in t:\n",
    "                window[c] += 1\n",
    "                if window[c] == need[c]:\n",
    "                    valid += 1\n",
    "            right += 1\n",
    "\n",
    "            while valid == len(need):\n",
    "                if right - left < length:\n",
    "                    start = left\n",
    "                    length = right - left\n",
    "                d = s[left]\n",
    "                if d in t:\n",
    "                    if window[d] == need[d]:\n",
    "                        valid -= 1\n",
    "                    window[d] -= 1\n",
    "                left += 1\n",
    "        return \"\" if length == float('inf') else s[start: start+length]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict\n",
    "class Solution:\n",
    "    def minWindow(self, s: str, t: str) -> str:\n",
    "        left, right = 0, 0\n",
    "        window1, window2 = defaultdict(int), defaultdict(int)\n",
    "        for i in t:\n",
    "            window2[i]+=1\n",
    "        needed = len(t)\n",
    "        res = '*'*len(s)\n",
    "        while right<len(s):\n",
    "            right+=1\n",
    "            cur = s[right-1]\n",
    "            if window2[cur]>0:\n",
    "                window1[cur] += 1\n",
    "                if window1[cur]<=window2[cur]:\n",
    "                    needed-=1\n",
    "            while needed==0:\n",
    "                if len(res)>=right-left:\n",
    "                    res = s[left:right]\n",
    "                cur = s[left]\n",
    "                left+=1\n",
    "                if window2[cur]>0:\n",
    "                    if window1[cur]<=window2[cur]:\n",
    "                        needed+=1\n",
    "                    window1[cur] -= 1\n",
    "        return res if res!='*'*len(s) else ''\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minWindow(self, s: str, t: str) -> str:\n",
    "        \n",
    "        m, n = len(s), len(t)\n",
    "        if m < n:\n",
    "            return ''\n",
    "        cnt = collections.Counter(t)\n",
    "        need = n\n",
    "\n",
    "        start, end = 0, -1\n",
    "        length = m + 1\n",
    "        j = 0\n",
    "        for i in range(m):\n",
    "            if s[i] in cnt:\n",
    "                if cnt[s[i]] > 0:\n",
    "                    need -= 1\n",
    "                cnt[s[i]] -= 1\n",
    "            \n",
    "            while need == 0:\n",
    "                if i - j + 1 < length:\n",
    "                    length = i - j + 1\n",
    "                    start, end = j, i\n",
    "                if s[j] in cnt:\n",
    "                    if cnt[s[j]] >= 0:\n",
    "                        need += 1\n",
    "                    cnt[s[j]] += 1\n",
    "                j += 1\n",
    "        return s[start:end+1]\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minWindow(self, s: str, t: str) -> str:\n",
    "        # 目标窗口字符数量\n",
    "        window = {w : t.count(w) for w in set(t)}\n",
    "        # 滑动窗口字符数量\n",
    "        need = {w : 0 for w in set(t)}\n",
    "\n",
    "        # 初始化双指针\n",
    "        left, right = 0, 0\n",
    "        valid = 0\n",
    "        # 记录最小覆盖字串的起始索引及长度\n",
    "        start = 0\n",
    "        length = float(\"inf\")\n",
    "        while right < len(s):\n",
    "            c = s[right]\n",
    "            right += 1\n",
    "            if c in window.keys():\n",
    "                need[c] += 1\n",
    "                if need[c] == window[c]:\n",
    "                    valid += 1\n",
    "            \n",
    "            while valid == len(window):\n",
    "                if right - left < length:\n",
    "                    start = left\n",
    "                    length = right - left\n",
    "                d = s[left]\n",
    "                left += 1\n",
    "                if d in window.keys():\n",
    "                    if need[d] == window[d]:\n",
    "                        valid -= 1\n",
    "                    need[d] -= 1\n",
    "        \n",
    "        return s[start: start + length] if length < float(\"inf\") else \"\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minWindow(self, s: str, t: str) -> str:\n",
    "        count = len(t)\n",
    "        need = {}\n",
    "        s_list = list(s)  # todo 删\n",
    "        for char in t:\n",
    "            need[char] = need.get(char, 0) + 1\n",
    "        maxL = 1e6\n",
    "        ans = ''\n",
    "        start = 0\n",
    "        for i, cur in enumerate(s):\n",
    "            if cur in need:\n",
    "                if need[cur] > 0:\n",
    "                    count -= 1\n",
    "                need[s[i]] -= 1\n",
    "                if count == 0:\n",
    "                    while start < i:\n",
    "                        if s[start] in need:\n",
    "                            if need[s[start]] == 0:\n",
    "                                break\n",
    "                            else:\n",
    "                                need[s[start]] += 1\n",
    "                        start += 1\n",
    "                    if i - start + 1 < maxL:\n",
    "                        ans = s[start: i + 1]\n",
    "                        maxL = i - start + 1\n",
    "                        need[s[start]] += 1\n",
    "                        start += 1\n",
    "                        count += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minWindow(self, s: str, t: str) -> str:\n",
    "        # 1. 先处理目标串\n",
    "        t_cnt = [0 for x in range(ord('z') - ord('A') + 1)]  # 目标串每个字母的出现个数\n",
    "        t_len = len(t)  # 目标串所有字母的出现个数\n",
    "        for c in t:\n",
    "            ci = ord(c) - ord('A')\n",
    "            t_cnt[ci] += 1\n",
    "\n",
    "        # 2. 双指针遍历源串\n",
    "        s_lst = [ord(c) - ord('A') for c in s]  # 2. 将源串转化为list，方便后续运算\n",
    "        s_len = len(s_lst)\n",
    "        min_found_str_be = []  # 最小发现位置\n",
    "        min_found_str_len = 100000  # 最小发现长度\n",
    "        b = 0  # 双指针之首指针\n",
    "        e = 0  # 双指针之尾指针，注意，这里是开区间，即[a,b)表达了源串的一个字串\n",
    "        s_cnt = [0 for x in range(ord('z') - ord('A') + 1)]  # 源串b,e之间，每个字母的出现个数\n",
    "        gap = t_len  # 源串b,e之间，所需要的目标字母还差多少个\n",
    "        while True:\n",
    "            assert(gap > 0)  # 一定会有缝隙。\n",
    "            # 1. 移动尾指针。\n",
    "            if e == s_len:  # 移动不了，就退出循环\n",
    "                break\n",
    "            ci = s_lst[e]  # 先取值\n",
    "            e += 1  # 移动尾指针\n",
    "            if s_cnt[ci] < t_cnt[ci]:  # 如果这移动是有效移动，即减少了缝隙，则缝隙减1\n",
    "                gap -= 1\n",
    "                assert(gap >= 0)\n",
    "            s_cnt[ci] += 1\n",
    "            if gap == 0:  # 这次移动尾指针，导致了缝隙为0，则当前收尾指针构成了一个结果。\n",
    "                assert(s_cnt[s_lst[b]] == t_cnt[s_lst[b]])  # 首指针指向的字母的个数，应该和目标字母个数相同。如果小，则不可能gap为0；如果大，则上次就应该收缩。\n",
    "                assert(e - b < min_found_str_len)  # 区间长度应该小于最小发现长度。如果等于或大于，早就应该收缩了。\n",
    "                min_found_str_len = e - b\n",
    "                min_found_str_be = [b, e]\n",
    "                assert(e - b >= t_len)\n",
    "                if e - b == t_len:  # 如果达到了极致，不可能有更短的了，就完成了。\n",
    "                    return s[b:e]\n",
    "            # 2. 考虑收缩，2个收缩条件满足其一即可收缩。1）首尾区间长度大于等于最小发现长度-1；2）首指针指向的字符是多余的；\n",
    "            while e - b >= min_found_str_len - 1 or s_cnt[s_lst[b]] > t_cnt[s_lst[b]]:\n",
    "                s_cnt[s_lst[b]] -= 1\n",
    "                assert(s_cnt[s_lst[b]] >= 0)\n",
    "                if s_cnt[s_lst[b]] < t_cnt[s_lst[b]]:  # 如果不多余(因长度而收缩)，收缩会导致缝隙加大\n",
    "                    gap += 1\n",
    "                    assert(gap <= t_len)\n",
    "                b += 1\n",
    "                assert(b <= e)\n",
    "                if b == s_len:  # 移动不了，就退出循环\n",
    "                    break\n",
    "\n",
    "        # 3. 返回最小发现串\n",
    "        if min_found_str_be:\n",
    "            return s[min_found_str_be[0]:min_found_str_be[1]]\n",
    "        else:\n",
    "            return \"\"\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minWindow(self, s: str, t: str) -> str:\n",
    "        \n",
    "        if len(t) > len(s):\n",
    "            return ''        \n",
    "        \n",
    "        cnt = collections.Counter(t)    # 哈希表：记录需要匹配到的各个元素的数目\n",
    "        need = len(t)                   # 记录需要匹配到的字符总数【need=0表示匹配到了】\n",
    "        \n",
    "        n = len(s)\n",
    "        start, end = 0, -1          # 记录目标子串s[start, end]的起始和结尾\n",
    "        min_len = n + 1             # 符合题意的最短子串长度【初始化为一个不可能的较大值】\n",
    "        left = right = 0            # 滑动窗口的左右边界\n",
    "        \n",
    "        for right in range(n):\n",
    "            \n",
    "            # 窗口右边界右移一位\n",
    "            ch = s[right]               # 窗口中新加入的字符\n",
    "            if ch in cnt:               # 新加入的字符位于t中\n",
    "                if cnt[ch] > 0:         # 对当前字符ch还有需求\n",
    "                    need -= 1           # 此时新加入窗口中的ch对need有影响\n",
    "                cnt[ch] -= 1\n",
    "            \n",
    "            # 窗口左边界持续右移\n",
    "            while need == 0:            # need=0，当前窗口完全覆盖了t\n",
    "                if right - left + 1 < min_len:      # 出现了更短的子串\n",
    "                    min_len = right - left + 1\n",
    "                    start, end = left, right\n",
    "                \n",
    "                ch = s[left]            # 窗口中要滑出的字符\n",
    "                if ch in cnt:           # 刚滑出的字符位于t中\n",
    "                    if cnt[ch] >= 0:    # 对当前字符ch还有需求，或刚好无需求(其实此时只有=0的情况)\n",
    "                        need += 1       # 此时滑出窗口的ch会对need有影响\n",
    "                    cnt[ch] += 1\n",
    "                left += 1               # 窗口左边界+1\n",
    "        \n",
    "        return s[start: end+1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minWindow(self, s: str, t: str) -> str:\n",
    "        if len(s) == 0:\n",
    "            return \"\"\n",
    "        \n",
    "    \n",
    "        target_dict = dict()\n",
    "        current_dict = dict()\n",
    "        for ch in t:\n",
    "            if ch in target_dict:\n",
    "                target_dict[ch] += 1\n",
    "            else:\n",
    "                target_dict[ch] = 1\n",
    "            current_dict[ch] = 0\n",
    "\n",
    "        # 滑动窗口遍历\n",
    "        left = 0\n",
    "        right = 0\n",
    "        start = 0\n",
    "        macth_size = 0\n",
    "        res = float(\"inf\")\n",
    "        while right < len(s):\n",
    "            cur_ch = s[right]\n",
    "            if cur_ch in target_dict:\n",
    "                current_dict[cur_ch] += 1\n",
    "                if current_dict[cur_ch] == target_dict[cur_ch]:\n",
    "                    macth_size += 1\n",
    "            # right += 1\n",
    "            # 判断当前窗口内是否match\n",
    "            # 当前窗口str s[left:right]\n",
    "            while macth_size == len(target_dict):\n",
    "                # match\n",
    "                if right-left+1 < res:\n",
    "                    res = right-left+1\n",
    "                    start = left\n",
    "                # 缩小窗口\n",
    "                left_ch = s[left]\n",
    "                if left_ch in target_dict:\n",
    "                    current_dict[left_ch] -= 1\n",
    "                    if current_dict[left_ch] < target_dict[left_ch]:\n",
    "                        macth_size -= 1\n",
    "                left += 1 # 窗口缩小\n",
    "            right += 1 # 窗口变大\n",
    "\n",
    "        match_str = s[start:start+res] if res < float(\"inf\") else \"\"\n",
    "        # print(start,res)\n",
    "        return match_str"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minWindow(self, s: str, t: str) -> str:\n",
    "        len_s, len_t = len(s), len(t)\n",
    "        if len_s < len_t: return \"\"\n",
    "\n",
    "        dic_t = defaultdict(int)\n",
    "        dic_s = defaultdict(int)\n",
    "        for c in t:\n",
    "            dic_t[c] += 1\n",
    "        \n",
    "        slow, res, cur, num = 0, len_s+1, \"\", 0\n",
    "        for fast in range(len_s):\n",
    "            dic_s[s[fast]] += 1\n",
    "            if dic_s[s[fast]] <= dic_t[s[fast]]:\n",
    "                num += 1   # 有效位\n",
    "            while slow<=fast and dic_s[s[slow]] > dic_t[s[slow]]:\n",
    "                dic_s[s[slow]] -= 1\n",
    "                slow += 1  # 收缩左边界\n",
    "            if num == len_t and fast-slow+1 < res:\n",
    "                res = fast-slow+1\n",
    "                cur = s[slow:fast+1]\n",
    "\n",
    "        return cur"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minWindow(self, s: str, t: str) -> str:\n",
    "        m, n = len(s), len(t)\n",
    "        t_dict = collections.Counter(t)\n",
    "        ans = [0, m-1]\n",
    "        left, test = 0, n\n",
    "        flag = False\n",
    "\n",
    "\n",
    "        for right in range(m):\n",
    "            ch = s[right]\n",
    "            if ch in t_dict:\n",
    "                if t_dict[ch] > 0:\n",
    "                    test -= 1    \n",
    "                t_dict[ch] -= 1\n",
    "            \n",
    "            if test == 0:\n",
    "                flag = True\n",
    "                while test == 0:\n",
    "                    ch = s[left]\n",
    "                    left += 1\n",
    "                    if ch in t_dict:\n",
    "                        if t_dict[ch] == 0:\n",
    "                            test += 1\n",
    "                        t_dict[ch] += 1\n",
    "                # print(big[left-1 : right + 1], small_dict)\n",
    "                if right - left + 1 < ans[1] - ans[0]:\n",
    "                    ans = [left - 1, right]\n",
    "        return s[ans[0]:ans[1]+ 1 ] if flag else \"\" "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minWindow(self, s: str, t: str) -> str:\n",
    "        n=len(s)\n",
    "        result=[[0,0],n+1]\n",
    "        right=0\n",
    "        word_dict=dict(Counter(t))\n",
    "        need=len(t)\n",
    "        for left in range(-1,n):\n",
    "            if right-left<result[1] and need==0:\n",
    "                result[0][0],result[0][1]=left,right\n",
    "                result[1]=right-left\n",
    "\n",
    "            if need==0:\n",
    "                if s[left] not in word_dict:\n",
    "                    continue\n",
    "                if word_dict[s[left]]<0:\n",
    "                    word_dict[s[left]]+=1\n",
    "                    continue\n",
    "                \n",
    "                elif word_dict[s[left]] == 0:\n",
    "                    need += 1\n",
    "                    word_dict[s[left]] += 1\n",
    "\n",
    "\n",
    "            while right<n and need>0:\n",
    "                if s[right] in word_dict:\n",
    "                    if word_dict[s[right]]>0:\n",
    "                        need-=1\n",
    "                    word_dict[s[right]]-=1\n",
    "                right+=1\n",
    "\n",
    "        return s[result[0][0]:result[0][1]]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import Counter\n",
    "class Solution:\n",
    "    def minWindow(self, s: str, t: str) -> str:\n",
    "        ns = len(s)\n",
    "        nt = len(t)\n",
    "        if ns < nt:\n",
    "            return \"\"\n",
    "        mini = float(\"inf\")\n",
    "        \n",
    "        satisfy = 0\n",
    "        left = right = 0\n",
    "        # 不满足右移，满足左移\n",
    "        ori = Counter(t)\n",
    "        buffer = {}\n",
    "        res = \"\"\n",
    "\n",
    "        while right != ns:\n",
    "            if s[right] not in buffer:\n",
    "                buffer[s[right]] = 1\n",
    "            else:\n",
    "                buffer[s[right]] += 1\n",
    "            if buffer[s[right]] == ori[s[right]]:\n",
    "                satisfy += 1\n",
    "            while satisfy == len(ori):\n",
    "                if right + 1 - left < mini:\n",
    "                    res = s[left:right + 1]\n",
    "                    mini = right + 1 - left\n",
    "                buffer[s[left]] -= 1\n",
    "                if buffer[s[left]] < ori[s[left]]:\n",
    "                    satisfy -= 1\n",
    "                left += 1\n",
    "            # print(f\"buffer is {buffer}, res is {res}, mini is {mini}, satisfy is {satisfy}\")\n",
    "            right += 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minWindow(self, s: str, t: str) -> str:\n",
    "        dict_t={}\n",
    "        dict_s={}\n",
    "        resl=0\n",
    "        resr=0\n",
    "        istrue=False\n",
    "        len1=len(s)\n",
    "        len2=len(t)\n",
    "        if len2>len1:\n",
    "            return \"\"\n",
    "        lmax=100000\n",
    "        right=0\n",
    "        for i in range(len2):\n",
    "            if t[i] not in dict_t.keys():\n",
    "                dict_t[t[i]]=1\n",
    "                dict_s[t[i]]=1\n",
    "            else:\n",
    "                dict_t[t[i]]+=1\n",
    "                dict_s[t[i]]+=1\n",
    "        for i in range(len1):\n",
    "            while not istrue and right<len1:\n",
    "                if s[right] in dict_s.keys():\n",
    "                    dict_s[s[right]]-=1\n",
    "                right+=1\n",
    "                istrue=True\n",
    "                for j in dict_s.keys():\n",
    "                    if dict_s[j]>0:\n",
    "                        istrue=False\n",
    "            if istrue:\n",
    "                if right-i < lmax:\n",
    "                    lmax=right-i\n",
    "                    resl=i\n",
    "                    resr=right\n",
    "            if s[i] in dict_s.keys():\n",
    "                dict_s[s[i]]+=1 \n",
    "            for j in dict_s.keys():\n",
    "                if dict_s[j]>0:\n",
    "                    istrue=False\n",
    "\n",
    "\n",
    "        return s[resl:resr]\n",
    "\n",
    "        \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minWindow(self, s: str, t: str) -> str:\n",
    "        def check(c,x):\n",
    "            for i,n in c.items():\n",
    "                if x.get(i) is None or x[i]<n: return False\n",
    "            return True\n",
    "        i,j=0,0\n",
    "        c=Counter(t)\n",
    "        x={}\n",
    "        if not check(c,Counter(s)): return \"\"\n",
    "        minimal=(0,len(s)-1)\n",
    "        flag=False\n",
    "        while j<len(s):\n",
    "            if x.get(s[j]) is not None:\n",
    "                x[s[j]]+=1\n",
    "            else:\n",
    "                x[s[j]]=1\n",
    "            if not flag:\n",
    "                flag=check(c,x)\n",
    "            while True:\n",
    "                x[s[i]]-=1\n",
    "                if check(c,x):\n",
    "                    i+=1\n",
    "                else:\n",
    "                    x[s[i]]+=1\n",
    "                    break\n",
    "            if flag and j-i<minimal[1]-minimal[0]: minimal=(i,j)\n",
    "            j+=1\n",
    "        return s[minimal[0]:minimal[1]+1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import collections\n",
    "class Solution:\n",
    "    def minWindow(self, s: str, t: str) -> str:\n",
    "        if len(t) > len(s):\n",
    "            return \"\"\n",
    "        # elif t == s[0]:\n",
    "        #     return t\n",
    "        \n",
    "        cnt = collections.Counter(t)\n",
    "        need = len(t)\n",
    "        n = len(s)\n",
    "        start = 0\n",
    "        end = -1\n",
    "        left = 0\n",
    "        min_len = n + 1\n",
    "        for right in range(n):\n",
    "            ch = s[right]\n",
    "            if ch in cnt:\n",
    "                if cnt[ch] > 0:\n",
    "                    need -= 1\n",
    "                cnt[ch] -= 1\n",
    "            \n",
    "            while need == 0:\n",
    "                if right - left + 1 < min_len:\n",
    "                    start, end = left, right\n",
    "                    min_len = right - left + 1\n",
    "                ch = s[left]\n",
    "                if ch in cnt:\n",
    "                    if cnt[ch] >= 0:\n",
    "                        need += 1\n",
    "                    cnt[ch] += 1\n",
    "                left += 1\n",
    "            \n",
    "        \n",
    "        return s[start:end + 1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minWindow(self, s: str, t: str) -> str:\n",
    "        def check(c,x):\n",
    "            for i,n in c.items():\n",
    "                if x.get(i) is None or x[i]<n: return False\n",
    "            return True\n",
    "        i,j=0,0\n",
    "        c=Counter(t)\n",
    "        x={}\n",
    "        if not check(c,Counter(s)): return \"\"\n",
    "        minimal=(0,len(s)-1)\n",
    "        flag=False\n",
    "        while j<len(s):\n",
    "            if x.get(s[j]) is not None:\n",
    "                x[s[j]]+=1\n",
    "            else:\n",
    "                x[s[j]]=1\n",
    "            if not flag:\n",
    "                flag=check(c,x)\n",
    "            while True:\n",
    "                x[s[i]]-=1\n",
    "                if check(c,x):\n",
    "                    i+=1\n",
    "                else:\n",
    "                    x[s[i]]+=1\n",
    "                    break\n",
    "            if flag and j-i<minimal[1]-minimal[0]: minimal=(i,j)\n",
    "            j+=1\n",
    "        return s[minimal[0]:minimal[1]+1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minWindow(self, s: str, t: str) -> str:\n",
    "        t_leng = len(t)\n",
    "        s_leng = len(s)\n",
    "        if t_leng > s_leng:\n",
    "            return \"\"\n",
    "        hash_map = {t[0]:1}\n",
    "        for i in range(1,len(t)):\n",
    "            if t[i] not in hash_map:\n",
    "                hash_map[t[i]] = 1\n",
    "            else:\n",
    "                hash_map[t[i]] += 1\n",
    "        start = left = right = 0\n",
    "        count = t_leng\n",
    "        size = s_leng\n",
    "        flag = False\n",
    "        for i in range(len(s)):\n",
    "            if s[i] in hash_map:\n",
    "                hash_map[s[i]] -= 1\n",
    "                if hash_map[s[i]] >=0:\n",
    "                    count -= 1\n",
    "                # print(hash_map)\n",
    "                # print(count)\n",
    "                # print(left)\n",
    "                # print(i)\n",
    "                if count != 0:\n",
    "                    continue\n",
    "                while count == 0:\n",
    "                    # print(left)\n",
    "                    if s[left] not in hash_map:\n",
    "                        left += 1\n",
    "                    else:\n",
    "                        hash_map[s[left]] += 1\n",
    "                        if hash_map[s[left]] > 0:\n",
    "                            count += 1\n",
    "                        left += 1\n",
    "                    # print(hash_map)\n",
    "                size_tmp = i-left+2\n",
    "                if size_tmp < size:\n",
    "                    # print(size)\n",
    "                    # print(left)\n",
    "                    size = size_tmp\n",
    "                    start = left-1\n",
    "            \n",
    "        # print(start)\n",
    "        # print(size)\n",
    "        # print(i)\n",
    "        # print(count)\n",
    "        # print(left)\n",
    "        if i == s_leng-1 and count !=0 and left == 0:\n",
    "            return \"\"\n",
    "        res = s[start:start+size]\n",
    "        return res\n",
    "                \n",
    "                    \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    # ADOBECODEBANC ABC\n",
    "    def minWindow(self, s: str, t: str) -> str:\n",
    "        s_len = len(s)\n",
    "        t_len = len(t)\n",
    "        t_str_map = {}\n",
    "        window_map = {}\n",
    "        for c in t:\n",
    "            t_str_map[c] = t_str_map.get(c, 0) + 1\n",
    "\n",
    "        def check():\n",
    "            for k, v in t_str_map.items():\n",
    "                if window_map.get(k, 0) < v:\n",
    "                    return False\n",
    "            return True\n",
    "        begin = -1\n",
    "        sub_length = float('inf')\n",
    "        left, right = 0, -1\n",
    "        while right < s_len:\n",
    "            right += 1\n",
    "            if right < s_len and s[right] in t_str_map:\n",
    "                window_map[s[right]] = window_map.get(s[right], 0) + 1\n",
    "            while check():\n",
    "                if right - left < sub_length:\n",
    "                    sub_length = min(right - left + 1, sub_length)\n",
    "                    begin = left\n",
    "                if s[left] in window_map:\n",
    "                    window_map[s[left]] -= 1\n",
    "                left += 1\n",
    "        return \"\" if begin == -1 else s[begin: begin + sub_length]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minWindow(self, s: str, t: str) -> str:\n",
    "        m,n = len(s),len(t)\n",
    "        l,r = 0,0\n",
    "        cnt = collections.Counter(t)\n",
    "        start,end = 0,-1\n",
    "        need = n\n",
    "        min_len = m+1\n",
    "        for r in range(m):\n",
    "            ch = s[r]\n",
    "            if ch in cnt:\n",
    "                if cnt[ch]>0:\n",
    "                    need -= 1\n",
    "                cnt[ch] -= 1\n",
    "            while need==0:\n",
    "                if r-l+1<min_len:\n",
    "                    min_len = r-l+1\n",
    "                    start,end=l,r\n",
    "                ch = s[l]\n",
    "                if ch in cnt:\n",
    "                    if cnt[ch]>=0:\n",
    "                        need+=1\n",
    "                    cnt[ch]+=1\n",
    "                l+=1\n",
    "        return s[start:end+1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minWindow(self, s: str, t: str) -> str:\n",
    "        dic1,dic2=Counter(),Counter(t)\n",
    "        #dic1,dic2 = defaultdict(int), defaultdict(int)\n",
    "        #for c in t:\n",
    "        #    dic2[c] += 1\n",
    "        l,r,val=0,0,0\n",
    "        m,n=float(\"inf\"),0\n",
    "        while r<len(s):\n",
    "            c=s[r]\n",
    "            r+=1\n",
    "            \n",
    "            if c in dic2:\n",
    "                dic1[c]+=1\n",
    "                if dic1[c]==dic2[c]:\n",
    "                    val+=1\n",
    "            while val==len(dic2):\n",
    "                d=s[l]\n",
    "                l+=1\n",
    "                if m-n>r-l:\n",
    "                    m,n=r,l-1\n",
    "                if d in dic2 :\n",
    "                    if dic1[d]==dic2[d]:\n",
    "                        val-=1\n",
    "                    dic1[d]-=1\n",
    "            \n",
    "        return \"\" if m==float(\"inf\") else s[n:m]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minWindow(self, s: str, t: str) -> str:\n",
    "        from collections import defaultdict\n",
    "        need,window=defaultdict(int),defaultdict(int)\n",
    "        for c in t:\n",
    "            need[c]+=1\n",
    "        \n",
    "        left,right=0,0\n",
    "        valid=0\n",
    "        length=float('inf')\n",
    "        start=0\n",
    "\n",
    "        while right<len(s):\n",
    "            c=s[right]\n",
    "            right+=1\n",
    "\n",
    "            if c in need:\n",
    "                window[c]+=1\n",
    "                if window[c]==need[c]:\n",
    "                    valid+=1\n",
    "            \n",
    "            while valid==len(need):\n",
    "                if right-left<length:\n",
    "                    start=left\n",
    "                    length=right-left\n",
    "                d=s[left]\n",
    "                left+=1\n",
    "                if d in need:\n",
    "                    if window[d]==need[d]:\n",
    "                        valid-=1\n",
    "                    window[d]-=1\n",
    "        \n",
    "        return '' if length==float('inf') else s[start:start+length]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    # 双指针\n",
    "    #滑动条件：满足条件，左滑；不满足，右滑\n",
    "    def minWindow(self, s: str, t: str) -> str:\n",
    "        len_s, len_t = len(s), len(t)\n",
    "        if len_s < len_t:\n",
    "            return ''\n",
    "        hashmap = Counter(t)\n",
    "        left=right = 0\n",
    "        res = ''  \n",
    "        count = len_t   # 记录需要匹配到的字符串总数\n",
    "        min_len = len_s + 1 # 初始化最短子串长度\n",
    "\n",
    "        while right < len_s:\n",
    "            # \n",
    "            if s[right] in hashmap:\n",
    "                if hashmap[s[right]] > 0:\n",
    "                    count -= 1\n",
    "                hashmap[s[right]] -= 1\n",
    "\n",
    "            while count == 0:\n",
    "                if right - left + 1 < min_len:\n",
    "                    min_len = right - left + 1\n",
    "                    res = s[left:right + 1]\n",
    "                if s[left] in hashmap:\n",
    "                    if hashmap[s[left]] >= 0:\n",
    "                        count += 1\n",
    "                    hashmap[s[left]] += 1\n",
    "                left += 1\n",
    "            right += 1\n",
    "        \n",
    "        return res\n",
    "\n",
    "                              \n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minWindow(self, s: str, t: str) -> str:\n",
    "        win = {}\n",
    "        need = {}\n",
    "        # initial need\n",
    "        for c in t:\n",
    "            if c in need:\n",
    "                need[c] += 1\n",
    "            else:\n",
    "                need[c] = 1\n",
    "                \n",
    "        left = 0\n",
    "        right = 0\n",
    "        valid = 0\n",
    "        min_left = 0\n",
    "        min_right = float(inf)\n",
    "        while right < len(s):\n",
    "            c = s[right]\n",
    "            right += 1\n",
    "            if c in need and need[c] > 0:\n",
    "                if c in win:\n",
    "                    win[c] += 1  \n",
    "                else:\n",
    "                    win[c] = 1\n",
    "\n",
    "                if need[c] == win[c]:\n",
    "                    valid += 1\n",
    "\n",
    "            while valid == len(need.keys()):\n",
    "                if (right - left) < (min_right - min_left):\n",
    "                    min_right = right\n",
    "                    min_left = left\n",
    "\n",
    "                #缩小窗口大小\n",
    "                d = s[left]\n",
    "                left += 1\n",
    "                if d in need:\n",
    "                    if win[d] == need[d]:\n",
    "                        valid -= 1\n",
    "                    win[d] -= 1\n",
    "\n",
    "        return \"\" if min_right > len(s) else s[min_left:min_right]\n",
    "                \n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minWindow(self, s: str, t: str) -> str:\n",
    "        win = {}\n",
    "        need = {}\n",
    "        # initial need\n",
    "        for c in t:\n",
    "            if c in need:\n",
    "                need[c] += 1\n",
    "            else:\n",
    "                need[c] = 1\n",
    "                \n",
    "        left = 0\n",
    "        right = 0\n",
    "        valid = 0\n",
    "        min_left = 0\n",
    "        min_right = float(inf)\n",
    "        while right < len(s):\n",
    "            c = s[right]\n",
    "            \n",
    "            if c in need and need[c] > 0:\n",
    "                if c in win:\n",
    "                    win[c] += 1  \n",
    "                else:\n",
    "                    win[c] = 1\n",
    "\n",
    "                if need[c] == win[c]:\n",
    "                    valid += 1\n",
    "\n",
    "            right += 1\n",
    "\n",
    "            while valid == len(need.keys()):\n",
    "                if (right - left) < (min_right - min_left):\n",
    "                    min_right = right\n",
    "                    min_left = left\n",
    "\n",
    "                #缩小窗口大小\n",
    "                d = s[left]\n",
    "                left += 1\n",
    "                if d in need:\n",
    "                    if win[d] == need[d]:\n",
    "                        valid -= 1\n",
    "                    win[d] -= 1\n",
    "\n",
    "            \n",
    "\n",
    "        return \"\" if min_right > len(s) else s[min_left:min_right]\n",
    "                \n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minWindow(self, s: str, t: str) -> str:\n",
    "        if len(t) > len(s): return \"\"\n",
    "        \n",
    "        hashh = {}\n",
    "        for ele in t:\n",
    "            if ele in hashh.keys(): hashh[ele] += 1\n",
    "            else: hashh[ele] = 1\n",
    "        \n",
    "        def judge_empty(hashh):\n",
    "            for ele in hashh.keys():\n",
    "                if hashh[ele] > 0: return False\n",
    "            return True\n",
    "        \n",
    "        \n",
    "        min_len = len(s) + 1\n",
    "        min_res = \"\"\n",
    "        i,j = 0,0\n",
    "        flag = True\n",
    "    \n",
    "\n",
    "        while i<len(s) and j<len(s):\n",
    "            if  flag and s[j] in hashh.keys(): hashh[s[j]] -= 1\n",
    "            if judge_empty(hashh):\n",
    "                if min_len > j-i+1:\n",
    "                    min_len = j-i+1\n",
    "                    min_res = s[i:j+1] \n",
    "\n",
    "                if s[i] in hashh.keys(): hashh[s[i]] += 1\n",
    "                i += 1\n",
    "                flag = False\n",
    "                \n",
    "            else:\n",
    "                flag = True\n",
    "                j += 1\n",
    "\n",
    "\n",
    "            \n",
    "        return min_res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minWindow(self, s: str, t: str) -> str:\n",
    "        sn = len(s)\n",
    "        tn = len(t)\n",
    "        \n",
    "        res_start = -1\n",
    "        res_len = float('inf')\n",
    "\n",
    "        need_cnt = tn\n",
    "        need_char_cnt = defaultdict(int)\n",
    "        for c in t:\n",
    "            need_char_cnt[c] += 1\n",
    "\n",
    "        l = 0\n",
    "        for r in range(sn):\n",
    "            if s[r] in need_char_cnt:\n",
    "                if need_char_cnt[s[r]] > 0:\n",
    "                    need_cnt -= 1\n",
    "                need_char_cnt[s[r]] -= 1\n",
    "            if need_cnt == 0:\n",
    "                while True: \n",
    "                    if s[l] not in need_char_cnt:\n",
    "                        l += 1\n",
    "                    else:\n",
    "                        if need_char_cnt[s[l]] < 0:\n",
    "                            need_char_cnt[s[l]] += 1\n",
    "                            l += 1\n",
    "                        else:\n",
    "                            break\n",
    "                cur_len = r - l + 1\n",
    "                if cur_len < res_len:\n",
    "                    res_len = cur_len\n",
    "                    res_start = l\n",
    "        if res_start != -1:\n",
    "            return s[res_start: res_start + res_len]\n",
    "        return \"\"\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def minWindow(self, s: str, t: str) -> str:\n",
    "        \n",
    "        if len(t) > len(s):\n",
    "            return ''               \n",
    "        cnt = collections.Counter(t)    # 哈希表：记录需要匹配到的各个元素的数目\n",
    "        need = len(t)                   # 记录需要匹配到的字符总数【need=0表示匹配到了】\n",
    "        \n",
    "        n = len(s)\n",
    "        start, end = 0, -1          # 记录目标子串s[start, end]的起始和结尾\n",
    "        min_len = n + 1             # 符合题意的最短子串长度【初始化为一个不可能的较大值】\n",
    "        left = right = 0            # 滑动窗口的左右边界\n",
    "        \n",
    "        for right in range(n):\n",
    "            \n",
    "            # 窗口右边界右移一位\n",
    "            ch = s[right]               # 窗口中新加入的字符\n",
    "            if ch in cnt:               # 新加入的字符位于t中\n",
    "                if cnt[ch] > 0:         # 对当前字符ch还有需求\n",
    "                    need -= 1           # 此时新加入窗口中的ch对need有影响\n",
    "                cnt[ch] -= 1\n",
    "            \n",
    "            # 窗口左边界持续右移\n",
    "            while need == 0:            # need=0，当前窗口完全覆盖了t\n",
    "                if right - left + 1 < min_len:      # 出现了更短的子串\n",
    "                    min_len = right - left + 1\n",
    "                    start, end = left, right\n",
    "                \n",
    "                ch = s[left]            # 窗口中要滑出的字符\n",
    "                if ch in cnt:           # 刚滑出的字符位于t中\n",
    "                    if cnt[ch] >= 0:    # 对当前字符ch还有需求，或刚好无需求(其实此时只有=0的情况)\n",
    "                        need += 1       # 此时滑出窗口的ch会对need有影响\n",
    "                    cnt[ch] += 1\n",
    "                left += 1               # 窗口左边界+1\n",
    "        \n",
    "        return s[start: end+1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minWindow(self, s: str, t: str) -> str:\n",
    "        n = len(s)\n",
    "        need = {}\n",
    "        win = {}\n",
    "        for w in t:\n",
    "            if w not in need:\n",
    "                need[w] = 1\n",
    "                win[w] = 0\n",
    "            else:\n",
    "                need[w] += 1\n",
    "        \n",
    "        l, r = 0, 0\n",
    "        l_min = n+1\n",
    "        start = 0\n",
    "        v = 0\n",
    "        while r < n:\n",
    "            c = s[r]\n",
    "            r += 1\n",
    "\n",
    "            if c in need:\n",
    "                win[c] += 1\n",
    "                if win[c] == need[c]:\n",
    "                    v += 1\n",
    "            \n",
    "            while v >= len(need):\n",
    "                if l_min >= (r-l):\n",
    "                    l_min = r - l\n",
    "                    start = l\n",
    "                \n",
    "                d = s[l]\n",
    "                l += 1\n",
    "                if d in need:\n",
    "                    if win[d] == need[d]:\n",
    "                        v -= 1\n",
    "                    win[d] -= 1\n",
    "                \n",
    "        if l_min == n+1: return \"\"\n",
    "        return s[start:start+l_min]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minWindow(self, s: str, t: str) -> str:\n",
    "        hashmapT = {}\n",
    "        m, n = len(s), len(t)\n",
    "        res = \"\"\n",
    "        if m < n:\n",
    "            return res\n",
    "        for i in range(n):\n",
    "            if t[i] in hashmapT:\n",
    "                hashmapT[t[i]] += 1\n",
    "            else:\n",
    "                hashmapT[t[i]] = 1\n",
    "        need = n\n",
    "        left = 0\n",
    "        for i in range(m):\n",
    "            cha = s[i]\n",
    "            if cha in hashmapT:\n",
    "                if hashmapT[cha] >= 1:\n",
    "                    need -= 1\n",
    "                hashmapT[cha] -= 1\n",
    "            while left <= i:\n",
    "                if s[left] in hashmapT and hashmapT[s[left]] < 0:\n",
    "                    hashmapT[s[left]] += 1\n",
    "                    left += 1\n",
    "                elif s[left] not in hashmapT:\n",
    "                    left += 1\n",
    "                else:\n",
    "                    break\n",
    "            if need == 0 and (i - left + 1 < len(res) or len(res) == 0):\n",
    "                res = s[left:i+1]\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# class Solution:\n",
    "#     # 双指针\n",
    "#     #滑动条件：满足条件，左滑；不满足，右滑\n",
    "#     def minWindow(self, s: str, t: str) -> str:\n",
    "#         len_s, len_t = len(s), len(t)\n",
    "#         if len_s < len_t:\n",
    "#             return False\n",
    "#         hashmap = Counter(t)\n",
    "#         left=right = 0\n",
    "#         res = []   \n",
    "#         count = len_t   # 记录需要匹配到的字符串总数\n",
    "#         min_len = len_t + 1 # 初始化最短子串长度\n",
    "\n",
    "#         while right < len_s:\n",
    "#             # \n",
    "#             if s[right] in hashmap:\n",
    "#                 if hashmap[s[right]] > 0:\n",
    "#                     count -= 1\n",
    "#                 hashmap[s[right]] -= 1\n",
    "\n",
    "#             while count == 0:\n",
    "#                 if right - left + 1 < len_s + 1:\n",
    "#                     min_len = right - left + 1\n",
    "#                     res = s[left:right + 1]\n",
    "#                 if s[left] in hashmap:\n",
    "#                     if hashmap[s[left]] >= 0:\n",
    "#                         count += 1\n",
    "#                     hashmap[s[left]] += 1\n",
    "#                 left += 1\n",
    "        \n",
    "#         return res\n",
    "\n",
    "                              \n",
    "class Solution:\n",
    "    def minWindow(self, s: str, t: str) -> str:\n",
    "        \n",
    "        if len(t) > len(s):\n",
    "            return ''        \n",
    "        \n",
    "        cnt = collections.Counter(t)    # 哈希表：记录需要匹配到的各个元素的数目\n",
    "        need = len(t)                   # 记录需要匹配到的字符总数【need=0表示匹配到了】\n",
    "        \n",
    "        n = len(s)\n",
    "        start, end = 0, -1          # 记录目标子串s[start, end]的起始和结尾\n",
    "        min_len = n + 1             # 符合题意的最短子串长度【初始化为一个不可能的较大值】\n",
    "        left = right = 0            # 滑动窗口的左右边界\n",
    "        \n",
    "        for right in range(n):\n",
    "            \n",
    "            # 窗口右边界右移一位\n",
    "            ch = s[right]               # 窗口中新加入的字符\n",
    "            if ch in cnt:               # 新加入的字符位于t中\n",
    "                if cnt[ch] > 0:         # 对当前字符ch还有需求\n",
    "                    need -= 1           # 此时新加入窗口中的ch对need有影响\n",
    "                cnt[ch] -= 1\n",
    "            \n",
    "            # 窗口左边界持续右移\n",
    "            while need == 0:            # need=0，当前窗口完全覆盖了t\n",
    "                if right - left + 1 < min_len:      # 出现了更短的子串\n",
    "                    min_len = right - left + 1\n",
    "                    start, end = left, right\n",
    "                \n",
    "                ch = s[left]            # 窗口中要滑出的字符\n",
    "                if ch in cnt:           # 刚滑出的字符位于t中\n",
    "                    if cnt[ch] >= 0:    # 对当前字符ch还有需求，或刚好无需求(其实此时只有=0的情况)\n",
    "                        need += 1       # 此时滑出窗口的ch会对need有影响\n",
    "                    cnt[ch] += 1\n",
    "                left += 1               # 窗口左边界+1\n",
    "        \n",
    "        return s[start: end+1]\n",
    "\n",
    "\n",
    "\n",
    "            \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minWindow(self, s: str, t: str) -> str:\n",
    "        l1, l2 = len(s), len(t)\n",
    "        if l2>l1:\n",
    "            return \"\"\n",
    "        \n",
    "        d1, d2 = defaultdict(int), defaultdict(int)\n",
    "        \n",
    "        for ch in t:\n",
    "            d2[ch] += 1\n",
    "        \n",
    "        for ch in s[:l2]:\n",
    "            d1[ch] += 1\n",
    "        \n",
    "        if d1==d2:  # 前边就匹上，则直接返回\n",
    "            return s[:l2]\n",
    "        \n",
    "        st = 0\n",
    "        rs = [0, l1+1]\n",
    "        for ch_idx in range(l2, l1):  # 右扩\n",
    "            cur_ch = s[ch_idx]\n",
    "            d1[cur_ch] += 1\n",
    "            for ch_k in d2:\n",
    "                if d1[ch_k]<d2[ch_k]:  # 比t中的少，则说明为包含\n",
    "                    break\n",
    "            else:  # 找到一个候选\n",
    "                # 左缩\n",
    "                ed = ch_idx\n",
    "                while st<=ed:\n",
    "                    left_ch = s[st]\n",
    "                    if d1[left_ch]==d2[left_ch]:  # 找到当前最短左边界\n",
    "                        if ed-st+1<rs[1]-rs[0]:\n",
    "                            rs[0], rs[1] = st, ed+1\n",
    "                        # 左边界去掉\n",
    "                        d1[left_ch] -= 1\n",
    "                        st += 1\n",
    "                        break\n",
    "\n",
    "                    d1[left_ch] -= 1\n",
    "                    st += 1\n",
    "        if rs[-1]<=l1:\n",
    "            return s[rs[0]:rs[1]]\n",
    "        return \"\"\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minWindow(self, s: str, t: str) -> str:\n",
    "        def check(maps,mapt):\n",
    "            #print(maps)\n",
    "            #print(mapt)\n",
    "            for k in mapt:\n",
    "                if maps[k]<mapt[k]:\n",
    "                    return False\n",
    "            return True\n",
    "\n",
    "        mapt={}\n",
    "        maps={}\n",
    "        for c in t:\n",
    "            if c in mapt:\n",
    "                mapt[c]+=1\n",
    "            else:\n",
    "                mapt[c]=1\n",
    "        for c in 'abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ':\n",
    "            maps[c]=0\n",
    "\n",
    "        left=0\n",
    "        right=0\n",
    "        minsen=''\n",
    "        maps[s[0]]=1\n",
    "        while right<len(s):\n",
    "            if check(maps,mapt):\n",
    "                while left+1<=right:\n",
    "                    tmp=s[left]\n",
    "                    if tmp not in t:\n",
    "                        left+=1\n",
    "                    elif  maps[tmp]-1>=mapt[tmp]:\n",
    "                        maps[tmp]-=1\n",
    "                        left+=1\n",
    "                    else:\n",
    "                        break\n",
    "                #print(s[left:right+1])\n",
    "                if minsen=='' or len(minsen)>len(s[left:right+1]):\n",
    "                    minsen=s[left:right+1]\n",
    "                    #print(left)\n",
    "                    #print(right)\n",
    "                    #print(minsen)\n",
    "                if left==right:\n",
    "                    maps[s[left]]-=1\n",
    "                    left+=1\n",
    "                    right+=1\n",
    "                else:\n",
    "                    maps[s[left]]-=1\n",
    "                    left+=1\n",
    "            else:\n",
    "                right+=1\n",
    "                if right<len(s):\n",
    "                    maps[s[right]]+=1\n",
    "\n",
    "        \n",
    "        if check(maps,mapt):\n",
    "            while left+1<=right:\n",
    "                tmp=s[left]\n",
    "                if tmp not in t:\n",
    "                    left+=1\n",
    "                elif  maps[tmp]-1>mapt[tmp]:\n",
    "                    maps[tmp]-=1\n",
    "                    left+=1\n",
    "                else:\n",
    "                    break\n",
    "            if minsen=='' or len(minsen)>len(s[left:right+1]):\n",
    "                minsen=s[left:right+1]\n",
    "        \n",
    "\n",
    "        return minsen\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minWindow(self, s: str, t: str) -> str:\n",
    "        m=len(s)\n",
    "        n=len(t)\n",
    "        temp=Counter(t)\n",
    "        left=start=end=0\n",
    "        for right,x in enumerate(s,1):\n",
    "            n-=temp[x]>0\n",
    "            temp[x]-=1\n",
    "            if n==0:\n",
    "                while left<right and temp[s[left]]<0:\n",
    "                    temp[s[left]]+=1\n",
    "                    left+=1\n",
    "                if not end or right-left<=end-start:\n",
    "                    end,start=right,left\n",
    "        return s[start:end]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minWindow(self, s: str, t: str) -> str:\n",
    "        N = len(s)\n",
    "\n",
    "        # 计算t中字母数字\n",
    "        ct = Counter(t)\n",
    "        NT = len(ct)\n",
    "\n",
    "        # 找第一个匹配的\n",
    "        num = 0\n",
    "        dp = defaultdict(int)\n",
    "\n",
    "        for r, c in enumerate(s):\n",
    "            if c in ct:\n",
    "                dp[c] += 1\n",
    "                if dp[c] == ct[c]:\n",
    "                    num += 1\n",
    "                    if num == NT:\n",
    "                        break\n",
    "        else:\n",
    "            return \"\"\n",
    "\n",
    "        l = 0\n",
    "        while 1:\n",
    "            c = s[l]\n",
    "            if c not in ct:\n",
    "                l += 1\n",
    "            elif dp[c] > ct[c]:\n",
    "                dp[c] -= 1\n",
    "                l += 1\n",
    "            else:\n",
    "                break\n",
    "\n",
    "        minLen = r - l + 1\n",
    "        mini = l\n",
    "\n",
    "        for r in range(r + 1, N):\n",
    "            c = s[r]\n",
    "            if c in ct:\n",
    "                dp[c] += 1\n",
    "\n",
    "                while 1:\n",
    "                    c = s[l]\n",
    "                    if c not in ct:\n",
    "                        l += 1\n",
    "                    elif dp[c] > ct[c]:\n",
    "                        dp[c] -= 1\n",
    "                        l += 1\n",
    "                    else:\n",
    "                        break\n",
    "\n",
    "                if r - l + 1 < minLen:\n",
    "                    minLen = r - l + 1\n",
    "                    mini = l\n",
    "\n",
    "        return s[mini:mini + minLen]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minWindow(self, s: str, t: str) -> str:\n",
    "        m, n, t_counter = len(s), len(t), collections.Counter(t)\n",
    "        min_len, res = inf, [0,0]\n",
    "\n",
    "        require, l = n, 0\n",
    "        # 初始化l到s中t字符第一位\n",
    "        while l<m and s[l] not in t_counter: l+=1\n",
    "        # 滑动窗口右侧遍历\n",
    "        for r in range(m):\n",
    "            char = s[r]\n",
    "            if char in t_counter:\n",
    "                # 右侧等于左侧时，判断该字符是否多余，多余则l右移到下一个数量相等/不足的字符\n",
    "                # 右侧不等于左侧，只有该字符不足时require-1，否则记录窗口内需求数量-1，继续滑动\n",
    "                if s[l]==char:\n",
    "                    if t_counter[char]>0: \n",
    "                        require-=1\n",
    "                        t_counter[char]-=1\n",
    "                    else:\n",
    "                        l+=1\n",
    "                        # 窗口内需求数量>=0的t字符为下一个左端点\n",
    "                        while t_counter.get(s[l], -1)<0: \n",
    "                            if s[l] in t_counter: t_counter[s[l]]+=1\n",
    "                            l+=1\n",
    "                else:\n",
    "                    if t_counter[char]>0:\n",
    "                        require-=1\n",
    "                    t_counter[char]-=1\n",
    "                # 注意：只在t字符处判断，因为端点一定为t字符\n",
    "                if require==0 and (r+1-l)<min_len: min_len, res = r-l+1, [l, r+1]\n",
    "\n",
    "        return s[res[0]:res[1]]\n",
    "\n",
    "            \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minWindow(self, s: str, t: str) -> str:\n",
    "        # 字符串、哈希表、滑动窗口\n",
    "        # window 不定宽\n",
    "        if len(s) < len(t):\n",
    "            return ''\n",
    "        from collections import Counter, defaultdict\n",
    "        need = Counter(t)\n",
    "        window = defaultdict(int)\n",
    "        left, right, start, valid, minlen = 0, 0, 0, 0, float('inf')\n",
    "        while right < len(s):\n",
    "            c = s[right]\n",
    "            right += 1\n",
    "            window[c] += 1\n",
    "            if window[c] == need[c]:\n",
    "                valid += 1\n",
    "            while len(need) == valid:\n",
    "                if right - left < minlen:\n",
    "                    minlen = right - left\n",
    "                    start = left\n",
    "                d = s[left]\n",
    "                left += 1\n",
    "                if window[d] == need[d]:\n",
    "                    valid -= 1\n",
    "                window[d] -= 1\n",
    "        if minlen == float('inf'):\n",
    "            return ''\n",
    "        else:\n",
    "            return s[start: start + minlen]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minWindow(self, s: str, t: str) -> str:\n",
    "        if len(t) > len(s): return ''        \n",
    "        \n",
    "        cnt = Counter(t)\n",
    "        need = len(t)\n",
    "        n = len(s)\n",
    "        start, end = 0, -1\n",
    "        min_len = inf\n",
    "        left = 0\n",
    "        for right in range(n):\n",
    "            ch = s[right]            \n",
    "            if ch in cnt:\n",
    "                if cnt[ch] > 0:\n",
    "                    need -= 1 \n",
    "                cnt[ch] -= 1\n",
    "            while need == 0:\n",
    "                if right - left + 1 < min_len:\n",
    "                    min_len = right - left + 1\n",
    "                    start, end = left, right\n",
    "                ch = s[left]\n",
    "                if ch in cnt:\n",
    "                    if cnt[ch] == 0:\n",
    "                        need += 1  \n",
    "                    cnt[ch] += 1\n",
    "                left += 1\n",
    "        \n",
    "        return s[start: end+1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import collections\n",
    "class Solution:\n",
    "    def minWindow(self, s: str, t: str) -> str:\n",
    "        dic = collections.Counter(t)\n",
    "        res_l = len(t)\n",
    "        l,r = 0,0\n",
    "        min_l = float('inf')\n",
    "        while r<len(s):\n",
    "            if s[r] in t:\n",
    "                if dic[s[r]]>0:\n",
    "                    res_l -=1 \n",
    "                dic[s[r]] -=1\n",
    "            while res_l==0:\n",
    "                if r-l+1<min_l:\n",
    "                    min_l = r-l+1\n",
    "                    l_bound = l\n",
    "                if s[l] in t:\n",
    "                    dic[s[l]] +=1\n",
    "                    if dic[s[l]]>0:\n",
    "                        res_l +=1                    \n",
    "                l+=1\n",
    "            r +=1\n",
    "        if min_l==float('inf'):\n",
    "            return ''\n",
    "        return s[l_bound:l_bound+min_l]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import Counter\n",
    "class Solution:\n",
    "    def minWindow(self, s: str, t: str) -> str:\n",
    "        if not t or not s:\n",
    "            return \"\"\n",
    "\n",
    "        # 字典t_dict记录t中字符的出现次数\n",
    "        t_dict = Counter(t)\n",
    "\n",
    "        required = len(t_dict)\n",
    "\n",
    "        # l, r为滑动窗口的左右边界\n",
    "        l, r = 0, 0\n",
    "\n",
    "        # formed用于记录当前窗口中满足t_dict条件的字符数量\n",
    "        formed = 0\n",
    "\n",
    "        window_counts = {}\n",
    "\n",
    "        ans = float(\"inf\"), None, None\n",
    "\n",
    "        while r < len(s):\n",
    "            character = s[r]\n",
    "            window_counts[character] = window_counts.get(character, 0) + 1\n",
    "\n",
    "            if character in t_dict and window_counts[character] == t_dict[character]:\n",
    "                formed += 1\n",
    "\n",
    "            # 尝试收缩窗口，直到它不再满足条件\n",
    "            while l <= r and formed == required:\n",
    "                character = s[l]\n",
    "\n",
    "                if r - l + 1 < ans[0]:\n",
    "                    ans = (r - l + 1, l, r)\n",
    "\n",
    "                window_counts[character] -= 1\n",
    "                if character in t_dict and window_counts[character] < t_dict[character]:\n",
    "                    formed -= 1\n",
    "\n",
    "                l += 1    \n",
    "            \n",
    "            r += 1\n",
    "\n",
    "        return \"\" if ans[0] == float(\"inf\") else s[ans[1]:ans[2] + 1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minWindow(self, s: str, t: str) -> str:\n",
    "        def check(maps,mapt):\n",
    "            #print(maps)\n",
    "            #print(mapt)\n",
    "            for k in mapt:\n",
    "                if maps[k]<mapt[k]:\n",
    "                    return False\n",
    "            return True\n",
    "\n",
    "        mapt={}\n",
    "        maps={}\n",
    "        for c in t:\n",
    "            if c in mapt:\n",
    "                mapt[c]+=1\n",
    "            else:\n",
    "                mapt[c]=1\n",
    "        for c in 'abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ':\n",
    "            maps[c]=0\n",
    "\n",
    "        left=0\n",
    "        right=0\n",
    "        minsen=''\n",
    "        maps[s[0]]=1\n",
    "        while right<len(s):\n",
    "            if check(maps,mapt):\n",
    "                while left+1<=right:\n",
    "                    tmp=s[left]\n",
    "                    if tmp not in t:\n",
    "                        left+=1\n",
    "                    elif  maps[tmp]-1>=mapt[tmp]:\n",
    "                        maps[tmp]-=1\n",
    "                        left+=1\n",
    "                    else:\n",
    "                        break\n",
    "                #print(s[left:right+1])\n",
    "                if minsen=='' or len(minsen)>len(s[left:right+1]):\n",
    "                    minsen=s[left:right+1]\n",
    "                    #print(left)\n",
    "                    #print(right)\n",
    "                    #print(minsen)\n",
    "                if left==right:\n",
    "                    maps[s[left]]-=1\n",
    "                    left+=1\n",
    "                    right+=1\n",
    "                else:\n",
    "                    maps[s[left]]-=1\n",
    "                    left+=1\n",
    "            else:\n",
    "                right+=1\n",
    "                if right<len(s):\n",
    "                    maps[s[right]]+=1\n",
    "\n",
    "        \n",
    "        if check(maps,mapt):\n",
    "            while left+1<=right:\n",
    "                tmp=s[left]\n",
    "                if tmp not in t:\n",
    "                    left+=1\n",
    "                elif  maps[tmp]-1>mapt[tmp]:\n",
    "                    maps[tmp]-=1\n",
    "                    left+=1\n",
    "                else:\n",
    "                    break\n",
    "            if minsen=='' or len(minsen)>len(s[left:right+1]):\n",
    "                minsen=s[left:right+1]\n",
    "        \n",
    "\n",
    "        return minsen\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict\n",
    "class Solution:\n",
    "    def minWindow(self, s: str, t: str) -> str:\n",
    "        len_s, len_t = len(s),len(t)\n",
    "        if len_s < len_t:\n",
    "            return \"\"\n",
    "\n",
    "        lookup = defaultdict(int)\n",
    "        cnt = len_t\n",
    "        for c in t:\n",
    "            lookup[c] += 1\n",
    "\n",
    "        i,j,min_len,start = 0,0,float(\"inf\"),0\n",
    "        while j<len_s:\n",
    "            while j < len_s and cnt > 0:\n",
    "                c = s[j]\n",
    "                if c in lookup:\n",
    "                    lookup[c] -= 1\n",
    "                    if lookup[c] >= 0:\n",
    "                        cnt -= 1\n",
    "                j += 1\n",
    "            \n",
    "            if cnt == 0 and j-i < min_len:\n",
    "                min_len = j-i\n",
    "                start = i\n",
    "            \n",
    "            while i < j and cnt == 0:\n",
    "                c = s[i]\n",
    "                if c in lookup:\n",
    "                    lookup[c] += 1\n",
    "                    if lookup[c] > 0:\n",
    "                        cnt += 1\n",
    "                i += 1\n",
    "                if cnt == 0 and j-i < min_len:\n",
    "                    min_len = j-i\n",
    "                    start = i\n",
    "            \n",
    "        return s[start:start+min_len] if min_len != float(\"inf\") else \"\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import Counter \n",
    "class Solution:\n",
    "    def minWindow(self, s: str, t: str) -> str:\n",
    "        main_str, sub_str = s, t\n",
    "        n, m = len(main_str), len(sub_str)\n",
    "        counter = Counter(sub_str)\n",
    "        need = m\n",
    "\n",
    "        left = 0\n",
    "        ans = \"\"\n",
    "        mini = float('inf')\n",
    "        for right in range(n):\n",
    "            ch = main_str[right]\n",
    "            if ch in counter:\n",
    "                if counter[ch] > 0:                 \n",
    "                    need -= 1\n",
    "                counter[ch] -= 1\n",
    "\n",
    "            while need == 0:\n",
    "                if right-left+1 < mini:\n",
    "                    mini = right-left+1\n",
    "                    ans = main_str[left: right+1]\n",
    "                \n",
    "                ch = main_str[left]\n",
    "                if ch in counter:\n",
    "                    if counter[ch] >= 0:\n",
    "                        need += 1\n",
    "                    counter[ch] += 1\n",
    "                left += 1\n",
    "        \n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minWindow(self, s: str, t: str) -> str:\n",
    "        from collections import Counter\n",
    "\n",
    "        # 部分case直接判断\n",
    "        if len(t) > len(s):\n",
    "            return \"\"\n",
    "    \n",
    "        # 构建map存储每个字符需要的个数 (alpha : num )\n",
    "        target_map = Counter(t)\n",
    "        # 数值，记录总共需要的个数，用于判断 是否满足题意\n",
    "        total_need = len(t)\n",
    "\n",
    "        # 初始化滑动窗口\n",
    "        l, r = 0, 0\n",
    "        # 初始化结果子串、最短长度\n",
    "        start, end = 0, -1\n",
    "        min_len = len(s) + 1\n",
    "\n",
    "        while r < len(s):\n",
    "            new_element = s[r]\n",
    "            if new_element in target_map:\n",
    "                # 如果这个字符还需要，把它放到中间结果，total_need更新\n",
    "                if target_map[new_element] > 0:\n",
    "                    total_need -= 1\n",
    "                target_map[new_element] -= 1  # 更新map\n",
    "\n",
    "            # 如果已经满足题意，尝试左边缩小窗口\n",
    "            while total_need == 0:\n",
    "                if r - l + 1 < min_len:\n",
    "                    start, end = l, r\n",
    "                    min_len = r - l + 1\n",
    "\n",
    "                drop_element = s[l]\n",
    "                if drop_element in target_map:\n",
    "                    if target_map[drop_element] == 0:\n",
    "                        # 如果刚好drop掉就不够了\n",
    "                        total_need += 1\n",
    "                    target_map[drop_element] += 1\n",
    "                l += 1\n",
    "\n",
    "            r += 1\n",
    "\n",
    "        return s[start: end+1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minWindow(self, s: str, t: str) -> str:\n",
    "        from collections import defaultdict\n",
    "\n",
    "        need, window = defaultdict(int), defaultdict(int)\n",
    "        for c in t:\n",
    "            need[c] += 1\n",
    "\n",
    "        left, right = 0, 0\n",
    "        valid = 0\n",
    "        # 记录最小覆盖子串的起始索引及长度\n",
    "        start, length = 0, float('inf')\n",
    "        while right < len(s):\n",
    "            # c 是将移入窗口的字符\n",
    "            c = s[right]\n",
    "            # 扩大窗口\n",
    "            right += 1\n",
    "            # 进行窗口内数据的一系列更新\n",
    "            if c in need:\n",
    "                window[c] += 1\n",
    "                if window[c] == need[c]:\n",
    "                    valid += 1\n",
    "\n",
    "            # 判断左侧窗口是否要收缩\n",
    "            while valid == len(need):\n",
    "                # 在这里更新最小覆盖子串\n",
    "                if right - left < length:\n",
    "                    start = left\n",
    "                    length = right - left\n",
    "\n",
    "                # d 是将移出窗口的字符\n",
    "                d = s[left]\n",
    "                # 缩小窗口\n",
    "                left += 1\n",
    "                # 进行窗口内数据的一系列更新\n",
    "                if d in need:\n",
    "                    if window[d] == need[d]:\n",
    "                        valid -= 1\n",
    "                    window[d] -= 1\n",
    "\n",
    "        # 返回最小覆盖子串\n",
    "        return \"\" if length == float('inf') else s[start:start + length]\n",
    "        \n",
    "            \n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minWindow(self, s: str, t: str) -> str:\n",
    "\n",
    "        left,right = 0,0\n",
    "        counter = collections.Counter(t)\n",
    "        need = len(t)\n",
    "        start,end = 0, -1\n",
    "        n = len(s)\n",
    "        min_length = n+1\n",
    "        for right in range(n):\n",
    "            ch = s[right]\n",
    "            if ch in counter:\n",
    "                if counter[ch]>0:\n",
    "                    need -= 1\n",
    "                counter[ch]-=1\n",
    "            \n",
    "            while need==0:\n",
    "                if right-left+1 < min_length:\n",
    "                    min_length = right-left+1\n",
    "                    start,end = left,right\n",
    "                ch = s[left]\n",
    "                if ch in counter:\n",
    "                    if counter[ch]>=0:\n",
    "                        need += 1\n",
    "                    counter[ch]+=1\n",
    "                left += 1\n",
    "\n",
    "        return s[start:end+1]\n",
    "         "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minWindow(self, s: str, t: str) -> str:\n",
    "        def check(maps,mapt):\n",
    "            #print(maps)\n",
    "            #print(mapt)\n",
    "            for k in mapt:\n",
    "                if maps[k]<mapt[k]:\n",
    "                    return False\n",
    "            return True\n",
    "\n",
    "        mapt={}\n",
    "        maps={}\n",
    "        for c in t:\n",
    "            if c in mapt:\n",
    "                mapt[c]+=1\n",
    "            else:\n",
    "                mapt[c]=1\n",
    "        for c in 'abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ':\n",
    "            maps[c]=0\n",
    "\n",
    "        left=0\n",
    "        right=0\n",
    "        minsen=''\n",
    "        maps[s[0]]=1\n",
    "        while right<len(s):\n",
    "            if check(maps,mapt):\n",
    "                while left+1<=right:\n",
    "                    tmp=s[left]\n",
    "                    if tmp not in t:\n",
    "                        left+=1\n",
    "                    elif  maps[tmp]-1>=mapt[tmp]:\n",
    "                        maps[tmp]-=1\n",
    "                        left+=1\n",
    "                    else:\n",
    "                        break\n",
    "                #print(s[left:right+1])\n",
    "                if minsen=='' or len(minsen)>len(s[left:right+1]):\n",
    "                    minsen=s[left:right+1]\n",
    "                    #print(left)\n",
    "                    #print(right)\n",
    "                    #print(minsen)\n",
    "                if left==right:\n",
    "                    maps[s[left]]-=1\n",
    "                    left+=1\n",
    "                    right+=1\n",
    "                else:\n",
    "                    maps[s[left]]-=1\n",
    "                    left+=1\n",
    "            else:\n",
    "                right+=1\n",
    "                if right<len(s):\n",
    "                    maps[s[right]]+=1\n",
    "\n",
    "        \n",
    "        \n",
    "\n",
    "        return minsen\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minWindow(self, s: str, t: str) -> str:\n",
    "        m, n = len(s), len(t)\n",
    "        if m < n:\n",
    "            return \"\"\n",
    "        res = \"\"\n",
    "        needCnt = n\n",
    "        need = defaultdict(int)\n",
    "        for c in t:\n",
    "            need[c] += 1\n",
    "        l = 0\n",
    "        min_len = float(inf)\n",
    "        for r, c in enumerate(s):\n",
    "            if need[c] > 0:\n",
    "                needCnt -= 1\n",
    "            need[c] -= 1\n",
    "            if needCnt == 0:\n",
    "                while need[s[l]] < 0:\n",
    "                    need[s[l]] += 1\n",
    "                    l += 1\n",
    "                if r-l+1 < min_len:\n",
    "                    min_len = r-l+1\n",
    "                    res = s[l: r+1]\n",
    "                needCnt += 1\n",
    "                need[s[l]] += 1\n",
    "                l += 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minWindow(self, s: str, t: str) -> str:\n",
    "        mapping = {}\n",
    "        for c in t:\n",
    "            if(c not in mapping):\n",
    "                mapping[c] = 1\n",
    "            else:\n",
    "                mapping[c] += 1\n",
    "        left, right = 0, 0\n",
    "        result = ''\n",
    "        minlen = float('inf')\n",
    "        cnt = len(mapping)\n",
    "        n = len(s)\n",
    "        while(right < n):\n",
    "            if(s[right] in mapping):\n",
    "                mapping[s[right]] -= 1\n",
    "                if(mapping[s[right]] == 0):\n",
    "                    cnt -= 1\n",
    "            while(left <= right and cnt == 0):\n",
    "                if(right-left+1 < minlen):\n",
    "                    minlen = right-left+1\n",
    "                    result = s[left:right+1]\n",
    "                if(s[left] in mapping):\n",
    "                    if(mapping[s[left]] == 0):\n",
    "                        cnt += 1\n",
    "                    mapping[s[left]] += 1\n",
    "                left += 1\n",
    "            right += 1\n",
    "        return result\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minWindow(self, s: str, t: str) -> str:\n",
    "        need = len(t)                   # 记录需要匹配到的字符总数【need=0表示匹配到了】\n",
    "        n = len(s)                \n",
    "        if need > n:\n",
    "            return ''        \n",
    "        \n",
    "        cnt = collections.Counter(t)    # 哈希表：记录需要匹配到的各个元素的数目\n",
    "        start, end = 0, -1          # 记录目标子串s[start, end]的起始和结尾\n",
    "        min_len = n + 1             # 符合题意的最短子串长度【初始化为一个不可能的较大值】\n",
    "        left = right = 0            # 滑动窗口的左右边界\n",
    "        ch=''\n",
    "        for right in range(n):  \n",
    "            # 窗口右边界右移一位\n",
    "            ch = s[right]               # 窗口中新加入的字符\n",
    "            if ch in cnt:               # 新加入的字符位于t中\n",
    "                if cnt[ch] > 0:         # 对当前字符ch还有需求\n",
    "                    need -= 1           # 此时新加入窗口中的ch对need有影响\n",
    "                cnt[ch] -= 1\n",
    "            \n",
    "            # 窗口左边界持续右移\n",
    "            while need == 0:            # need=0，当前窗口完全覆盖了t\n",
    "                if right - left + 1 < min_len:      # 出现了更短的子串\n",
    "                    min_len = right - left + 1\n",
    "                    start, end = left, right\n",
    "                \n",
    "                ch = s[left]            # 窗口中要滑出的字符\n",
    "                if ch in cnt:           # 刚滑出的字符位于t中\n",
    "                    if cnt[ch] >= 0:    # 对当前字符ch还有需求，或刚好无需求(其实此时只有=0的情况)\n",
    "                        need += 1       # 此时滑出窗口的ch会对need有影响\n",
    "                    cnt[ch] += 1\n",
    "                left += 1               # 窗口左边界+1\n",
    "        \n",
    "        return s[start: end+1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minWindow(self, s: str, t: str) -> str:\n",
    "        sn = len(s)\n",
    "        tn = len(t)\n",
    "        \n",
    "        res_start = -1\n",
    "        res_len = float('inf')\n",
    "\n",
    "        need_cnt = tn\n",
    "        need_char_cnt = defaultdict(int)\n",
    "        for c in t:\n",
    "            need_char_cnt[c] += 1\n",
    "\n",
    "        l = 0\n",
    "        for r in range(sn):\n",
    "            if s[r] in need_char_cnt:\n",
    "                if need_char_cnt[s[r]] > 0:\n",
    "                    need_cnt -= 1\n",
    "                need_char_cnt[s[r]] -= 1\n",
    "            if need_cnt == 0:\n",
    "                while True: \n",
    "                    if s[l] not in need_char_cnt:\n",
    "                        l += 1\n",
    "                    else:\n",
    "                        if need_char_cnt[s[l]] < 0:\n",
    "                            need_char_cnt[s[l]] += 1\n",
    "                            l += 1\n",
    "                        else:\n",
    "                            break\n",
    "                cur_len = r - l + 1\n",
    "                if cur_len < res_len:\n",
    "                    res_len = cur_len\n",
    "                    res_start = l\n",
    "        if res_start != -1:\n",
    "            return s[res_start: res_start + res_len]\n",
    "        return \"\"\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minWindow(self, s: str, t: str) -> str:\n",
    "        if len(s) < len(t): return \"\"\n",
    "\n",
    "        cnt = Counter(t)\n",
    "        need = len(t)\n",
    "        min_len = len(s)\n",
    "\n",
    "        start, end = 0, -1\n",
    "        left = 0\n",
    "\n",
    "        for right in range(len(s)):\n",
    "            _s = s[right]\n",
    "            if _s in t:\n",
    "                if cnt[_s] > 0:\n",
    "                    need -= 1\n",
    "                cnt[_s] -= 1\n",
    "\n",
    "            while need == 0:\n",
    "                if right - left + 1 <=  min_len:\n",
    "                    min_len = right - left + 1\n",
    "                    start, end = left, right\n",
    "                \n",
    "                _s = s[left]\n",
    "                if _s in t:\n",
    "                    if cnt[_s] >= 0:\n",
    "                        need += 1\n",
    "                    cnt[_s] += 1\n",
    "                left += 1\n",
    "\n",
    "        return s[start : end+1]\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minWindow(self, s: str, t: str) -> str:\n",
    "        n = len(s)\n",
    "        if n < len(t):\n",
    "            return ''\n",
    "        cnt = defaultdict(int)\n",
    "        need = 0\n",
    "        for ch in t:\n",
    "            if cnt[ch] == 0:\n",
    "                need += 1\n",
    "            cnt[ch] += 1\n",
    "        \n",
    "        left, right = -1, n\n",
    "        l = 0\n",
    "        for r, ch in enumerate(s):\n",
    "            if ch not in cnt:\n",
    "                continue\n",
    "            cnt[ch] -= 1\n",
    "            if cnt[ch] == 0:\n",
    "                need -= 1\n",
    "            while need == 0:\n",
    "                if s[l] in cnt:\n",
    "                    if cnt[s[l]] == 0:\n",
    "                        break\n",
    "                    cnt[s[l]] += 1\n",
    "                l += 1\n",
    "            if need == 0:\n",
    "                if r - l < right - left:\n",
    "                    left, right = l, r\n",
    "        \n",
    "        return s[left:right+1] if left != -1 else ''\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minWindow(self, s: str, t: str) -> str:\n",
    "        l1, l2 = len(s), len(t)\n",
    "        if l2>l1:\n",
    "            return \"\"\n",
    "        \n",
    "        d1, d2 = defaultdict(int), defaultdict(int)\n",
    "        \n",
    "        for ch in t:\n",
    "            d2[ch] += 1\n",
    "        \n",
    "        rs = [0, l1+1]\n",
    "        st = 0\n",
    "        for idx, ch in enumerate(s):  # 右扩\n",
    "            if d2[ch]>0:  # 该字符在t中还有，则待匹个数（还需多少字符匹配上t）-1\n",
    "                l2 -= 1\n",
    "            d2[ch] -= 1  # 尝试与t抵消，有就消，没有就欠着\n",
    "            if l2==0:  # 正好包含t，则尝试左缩\n",
    "                while st<=idx:\n",
    "                    left_ch = s[st]\n",
    "                    if d2[left_ch]==0:  # 找到当前最短左边界\n",
    "                        break\n",
    "                    # 左缩，左边字符从d2中取出\n",
    "                    d2[left_ch] += 1\n",
    "                    st += 1\n",
    "                if idx-st+1<rs[1]-rs[0]:  # 更短\n",
    "                    rs[0], rs[1] = st, idx+1\n",
    "                \n",
    "                # 从左边界下一个位置开始继续找，左边界还给d2，相应的待匹个数+1\n",
    "                d2[s[st]] += 1\n",
    "                l2 += 1\n",
    "                st += 1\n",
    "        return \"\" if rs[-1]>l1 else s[rs[0]:rs[1]]\n",
    "            \n",
    "        \n",
    "        # for ch in s[:l2]:\n",
    "        #     d1[ch] += 1\n",
    "        \n",
    "        # if d1==d2:  # 前边就匹上，则直接返回\n",
    "        #     return s[:l2]\n",
    "        \n",
    "        # st = 0\n",
    "        # rs = [0, l1+1]\n",
    "        # for ch_idx in range(l2, l1):  # 右扩\n",
    "        #     cur_ch = s[ch_idx]\n",
    "        #     d1[cur_ch] += 1\n",
    "        #     for ch_k in d2:\n",
    "        #         if d1[ch_k]<d2[ch_k]:  # 比t中的少，则说明为包含\n",
    "        #             break\n",
    "        #     else:  # 找到一个候选\n",
    "        #         # 左缩\n",
    "        #         ed = ch_idx\n",
    "        #         while st<=ed:\n",
    "        #             left_ch = s[st]\n",
    "        #             if d1[left_ch]==d2[left_ch]:  # 找到当前最短左边界\n",
    "        #                 if ed-st+1<rs[1]-rs[0]:\n",
    "        #                     rs[0], rs[1] = st, ed+1\n",
    "        #                 # 左边界去掉\n",
    "        #                 d1[left_ch] -= 1\n",
    "        #                 st += 1\n",
    "        #                 break\n",
    "\n",
    "        #             d1[left_ch] -= 1\n",
    "        #             st += 1\n",
    "        # if rs[-1]<=l1:\n",
    "        #     return s[rs[0]:rs[1]]\n",
    "        # return \"\"\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minWindow(self, s: str, t: str) -> str:\n",
    "\n",
    "        start,end = 0,-1\n",
    "        counter = collections.Counter(t)\n",
    "        num_count = len(t)\n",
    "        n = len(s)\n",
    "        right = left = 0\n",
    "        min_length = n+1\n",
    "        for right in range(n):\n",
    "            ch = s[right]\n",
    "            if ch in counter:\n",
    "                if counter[ch]>0:\n",
    "                    num_count -= 1\n",
    "                counter[ch]-=1\n",
    "            while num_count==0:\n",
    "                if right-left+1<min_length:\n",
    "                    min_length = right-left +1\n",
    "                    start,end = left,right\n",
    "                ch =s[left]\n",
    "                if ch in counter:\n",
    "                    if counter[ch]>=0:\n",
    "                        num_count+=1\n",
    "                    counter[ch] += 1\n",
    "                left += 1\n",
    "        return s[start:end+1]\n",
    "\n",
    "            \n",
    "         "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minWindow(self, s: str, t: str) -> str:\n",
    "        n, m = len(s), len(t)\n",
    "        if n < m:\n",
    "            return \"\"\n",
    "        need_count = {}\n",
    "        for i in t:\n",
    "            if i not in need_count:\n",
    "                need_count[i]=1\n",
    "            else:\n",
    "                need_count[i]+=1\n",
    "        curr_count= {}\n",
    "        # init curr_count\n",
    "        for c in need_count:\n",
    "            curr_count[c] = 0\n",
    "        #print(need_count, \"-->\", curr_count)\n",
    "        l,r = 0,0\n",
    "        vaild_c = 0\n",
    "        min_len = float('inf')\n",
    "        min_r = float('inf')\n",
    "        for r in range(n):\n",
    "            if s[r] in need_count:\n",
    "                curr_count[s[r]]+=1\n",
    "            if s[r] in curr_count and curr_count[s[r]] == need_count[s[r]]:\n",
    "                vaild_c +=1\n",
    "                \n",
    "            while vaild_c == len(need_count) and l <= r:\n",
    "                #print(l ,\"-->\",r, \" --: \",curr_count)\n",
    "                # 满足规则的情况下尝试缩小结果集合\n",
    "                p = s[l]\n",
    "                if min_len > r -l + 1:\n",
    "                    min_len = r - l +1\n",
    "                    min_r = r \n",
    "                l+=1 # 不管存不存在，夹逼准则都尽量的往右边挺进，寻求逼近真理的最优解释\n",
    "                if p in curr_count:\n",
    "                    if curr_count[p] >= need_count[p]:\n",
    "                        curr_count[p]-=1\n",
    "                        if curr_count[p] < need_count[p]:\n",
    "                            vaild_c -=1\n",
    "                            break\n",
    "        # 以min_r为结尾，长度为min_len的字符串，就是最小覆盖子串\n",
    "        #print(min_r, min_len)\n",
    "        if min_len == float('INF'):\n",
    "            return \"\"\n",
    "        return s[min_r-min_len+1:min_r+1]\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    def minWindow(self, s: str, t: str) -> str:\n",
    "\n",
    "        # 选用字典记录所需和窗口中的数据\n",
    "        need, window = defaultdict(int), defaultdict(int)\n",
    "        for ch in t:                # 初始化所需数据\n",
    "            need[ch] += 1\n",
    "\n",
    "        left, right = 0, 0          # 声明滑动窗口的左右指针\n",
    "        valid = 0                   # 窗口中满足所需字符的计数器\n",
    "\n",
    "        start, length = 0, float('inf')     # 记录最小覆盖子串的起始索引及长度\n",
    "\n",
    "        while right < len(s):\n",
    "            # 移入窗口\n",
    "            c_in = s[right]         # c_in是移入窗口的字符\n",
    "            right += 1              # 扩大窗口\n",
    "            if c_in in need:        # 移入窗口的更新维护操作\n",
    "                window[c_in] += 1\n",
    "                if window[c_in] == need[c_in]:\n",
    "                    valid += 1      # 达到需求,满足计数器加一\n",
    "\n",
    "            # 判断左侧窗口是否需要收缩\n",
    "            while valid == len(need):\n",
    "\n",
    "                # 更新最小覆盖子串\n",
    "                if right - left < length:\n",
    "                    start = left\n",
    "                    length = right - left\n",
    "\n",
    "                c_out = s[left]     # c_out是移出窗口的字符\n",
    "                left += 1           # 缩小窗口\n",
    "                if c_out in need:   # 移出窗口的更新维护操作\n",
    "                    if window[c_out] == need[c_out]:\n",
    "                        valid -= 1  # 移出后就不满足需求,满足计数器减一\n",
    "                    window[c_out] -= 1\n",
    "\n",
    "        return '' if length == float('inf') else s[start:(start+length)]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minWindow(self, s: str, t: str) -> str:\n",
    "        s_len = len(s)\n",
    "        t_len = len(t)\n",
    "        if t_len > s_len:\n",
    "            return \"\"\n",
    "        t_map = defaultdict(int)\n",
    "        s_map = defaultdict(int)\n",
    "        for i in range(t_len):\n",
    "            t_map[t[i]] += 1\n",
    "            s_map[s[i]] += 1\n",
    "        s_map[s[t_len - 1]] -= 1\n",
    "        def match():\n",
    "            for k, v in t_map.items():\n",
    "                if s_map[k] < v:\n",
    "                    return False\n",
    "            return True\n",
    "\n",
    "        begin, max_length = -1, float('inf')\n",
    "        left, right = 0, t_len - 1\n",
    "        while right < s_len:\n",
    "            s_map[s[right]] += 1\n",
    "            right += 1\n",
    "            while match():\n",
    "                if right - left < max_length:\n",
    "                    begin = left\n",
    "                    max_length = right - left\n",
    "                s_map[s[left]] -= 1\n",
    "                left += 1\n",
    "        return \"\" if begin == -1 else s[begin: begin + max_length]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minWindow(self, s: str, t: str) -> str:\n",
    "        \n",
    "        if len(t) > len(s):\n",
    "            return ''        \n",
    "        \n",
    "        cnt = collections.Counter(t)    # 哈希表：记录需要匹配到的各个元素的数目\n",
    "        need = len(t)                   # 记录需要匹配到的字符总数【need=0表示匹配到了】\n",
    "        \n",
    "        n = len(s)\n",
    "        start, end = 0, -1          # 记录目标子串s[start, end]的起始和结尾\n",
    "        min_len = n + 1             # 符合题意的最短子串长度【初始化为一个不可能的较大值】\n",
    "        left = right = 0            # 滑动窗口的左右边界\n",
    "        \n",
    "        for right in range(n):\n",
    "            \n",
    "            # 窗口右边界右移一位\n",
    "            ch = s[right]               # 窗口中新加入的字符\n",
    "            if ch in cnt:               # 新加入的字符位于t中\n",
    "                if cnt[ch] > 0:         # 对当前字符ch还有需求\n",
    "                    need -= 1           # 此时新加入窗口中的ch对need有影响\n",
    "                cnt[ch] -= 1\n",
    "            \n",
    "            # 窗口左边界持续右移\n",
    "            while need == 0:            # need=0，当前窗口完全覆盖了t\n",
    "                if right - left + 1 < min_len:      # 出现了更短的子串\n",
    "                    min_len = right - left + 1\n",
    "                    start, end = left, right\n",
    "                \n",
    "                ch = s[left]            # 窗口中要滑出的字符\n",
    "                if ch in cnt:           # 刚滑出的字符位于t中\n",
    "                    if cnt[ch] >= 0:    # 对当前字符ch还有需求，或刚好无需求(其实此时只有=0的情况)\n",
    "                        need += 1       # 此时滑出窗口的ch会对need有影响\n",
    "                    cnt[ch] += 1\n",
    "                left += 1               # 窗口左边界+1\n",
    "        \n",
    "        return s[start: end+1]\n",
    "\n",
    " "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minWindow(self, s: str, t: str) -> str:\n",
    "        if len(t)>len(s):\n",
    "            return ''\n",
    "        def ddd(d2,d1):\n",
    "            for i in range(len(d2)):\n",
    "                if d1[i]>d2[i]:\n",
    "                    return False\n",
    "            return True\n",
    "        d1,d2 = [0]*100,[0]*100\n",
    "        for i in range(len(t)):\n",
    "            d1[ord(t[i])-ord('A')]+=1\n",
    "            d2[ord(s[i])-ord('A')]+=1\n",
    "\n",
    "        if ddd(d2,d1):\n",
    "            return s[:len(t)]\n",
    "        i ,out= 0, ''\n",
    "        m = inf\n",
    "\n",
    "        for j in range(len(t),len(s)):\n",
    "            # if d2>=d1:\n",
    "            d2[ord(s[j])-ord('A')]+=1\n",
    "\n",
    "            while ddd(d2,d1):\n",
    "                # print(i,j,s[i:j+1])\n",
    "                if j-i+1<m:\n",
    "                    m = j-i+1\n",
    "                    out = s[i:j+1]\n",
    "                d2[ord(s[i])-ord('A')]-=1\n",
    "                i+=1\n",
    "                # print(d2[:5],d1[:5])\n",
    "\n",
    "            \n",
    "        return out\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minWindow(self, s: str, t: str) -> str:\n",
    "        s_len = len(s)\n",
    "        t_len = len(t)\n",
    "        if t_len > s_len:\n",
    "            return \"\"\n",
    "        begin, max_length = -1, float('inf')\n",
    "        left, right = 0, -1\n",
    "        t_map = {}\n",
    "        s_map = {}\n",
    "        for c in t:\n",
    "            t_map[c] = t_map.get(c, 0) + 1\n",
    "\n",
    "        def check():\n",
    "            for key, value in t_map.items():\n",
    "                if key not in s_map or s_map[key] < value:\n",
    "                    return False\n",
    "            return True\n",
    "\n",
    "        while right < s_len:\n",
    "            right += 1\n",
    "            if right < s_len:\n",
    "                s_map[s[right]] = s_map.get(s[right], 0) + 1\n",
    "            while check() and left <= right:\n",
    "                if right - left + 1 < max_length:\n",
    "                    max_length = right - left + 1\n",
    "                    begin = left\n",
    "                s_map[s[left]] -= 1\n",
    "                left += 1\n",
    "\n",
    "        return s[begin: begin + max_length] if begin != -1 else \"\"\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minWindow(self, s: str, t: str) -> str:\n",
    "        n = len(s)\n",
    "        if n < len(t):\n",
    "            return ''\n",
    "        cnt = defaultdict(int)\n",
    "        need = 0\n",
    "        for ch in t:\n",
    "            if cnt[ch] == 0:\n",
    "                need += 1\n",
    "            cnt[ch] += 1\n",
    "        \n",
    "        left, right = -1, n\n",
    "        ans = ''\n",
    "        l = 0\n",
    "        for r, ch in enumerate(s):\n",
    "            if ch not in cnt:\n",
    "                continue\n",
    "            cnt[ch] -= 1\n",
    "            if cnt[ch] == 0:\n",
    "                need -= 1\n",
    "            while need == 0:\n",
    "                if s[l] in cnt:\n",
    "                    if cnt[s[l]] == 0:\n",
    "                        break\n",
    "                    cnt[s[l]] += 1\n",
    "                l += 1\n",
    "            if need == 0:\n",
    "                if r - l < right - left:\n",
    "                    left, right = l, r\n",
    "        \n",
    "        return s[left:right+1] if left != -1 else ''\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minWindow(self, s: str, t: str) -> str:\n",
    "        need = {}\n",
    "        count = {}\n",
    "        for i in t:\n",
    "            need[i] = 0\n",
    "            count[i] = 0\n",
    "        for i in t:\n",
    "            need[i] += 1\n",
    "\n",
    "        left = right = start = 0\n",
    "        l = lenth = 0\n",
    "        tlen = len(need)\n",
    "        match = 0\n",
    "        for j in s:\n",
    "            cr = s[right]\n",
    "            right += 1\n",
    "            if need.get(cr,0)!=0:\n",
    "                count[cr] += 1\n",
    "                if count[cr]==need[cr]:\n",
    "                    match += 1\n",
    "            while match==tlen:\n",
    "                l = right - left\n",
    "                if lenth==0 or lenth>l:\n",
    "                    lenth = l\n",
    "                    start = left\n",
    "                cl = s[left]\n",
    "                left += 1\n",
    "                if need.get(cl,0)!=0:\n",
    "                    count[cl] -= 1\n",
    "                    if need[cl]>count[cl]:\n",
    "                        match -= 1\n",
    "\n",
    "        return s[start:start+lenth]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minWindow(self, s: str, t: str) -> str:\n",
    "        res = {}\n",
    "        need = {}\n",
    "        win = {}\n",
    "        valid = 0\n",
    "        length = float(\"inf\")\n",
    "        for i in t:\n",
    "            need[i] = need.get(i,0)+1\n",
    "        left, right = 0,0\n",
    "        while right<len(s):\n",
    "            c= s[right]\n",
    "            right+=1\n",
    "            if c in need:\n",
    "                win[c] =win.get(c, 0)+1\n",
    "                if win[c]==need[c]:\n",
    "                    valid+=1\n",
    "            while len(need)==valid:\n",
    "                if right-left<length:\n",
    "                    length = right-left\n",
    "                    start = left\n",
    "                d = s[left]\n",
    "                left+=1\n",
    "                if d in need:\n",
    "                    if need[d]==win[d]:\n",
    "                        valid-=1\n",
    "                    win[d]-=1\n",
    "        return \"\" if length==float(\"inf\") else s[start:start+length]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minWindow(self, s: str, t: str) -> str:\n",
    "        n = len(s)\n",
    "        m = len(t)\n",
    "        if m > n :\n",
    "            return \"\"\n",
    "        cnt = collections.Counter(t)\n",
    "        need = m\n",
    "        start, end = 0, -1\n",
    "        left, right = 0, 0\n",
    "        min_len = n + 1\n",
    "        while right < n :\n",
    "            ch = s[right]\n",
    "            if ch in cnt :\n",
    "                if cnt[ch] > 0 :\n",
    "                    need -= 1\n",
    "                cnt[ch] -= 1\n",
    "            while need == 0 :\n",
    "                if right - left + 1 < min_len :\n",
    "                    start, end = left, right\n",
    "                    min_len = right - left + 1\n",
    "                ch = s[left]\n",
    "                if ch in cnt :\n",
    "                    if cnt[ch] >= 0 :\n",
    "                        need += 1\n",
    "                    cnt[ch] += 1\n",
    "                left += 1\n",
    "            right += 1\n",
    "        return s[start: end + 1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minWindow(self, s: str, t: str) -> str:\n",
    "        \"\"\"\n",
    "        滑动窗口\n",
    "        \"\"\"\n",
    "        if not s and not t:\n",
    "            return \"\"\n",
    "        if not s:\n",
    "            return \"\"\n",
    "        if not t:\n",
    "            return \"\"\n",
    "        windows, needs = {}, {}\n",
    "        for ch in t:\n",
    "            needs[ch] = needs.get(ch, 0) + 1\n",
    "        rear, front = 0, 0\n",
    "        valid = 0\n",
    "        minLen = len(s) + 1\n",
    "        res = \"\"\n",
    "        # 开启滑动窗口\n",
    "        while front < len(s):\n",
    "            # 临时保存当前位置元素\n",
    "            temp = s[front]\n",
    "            # 扩大窗口\n",
    "            front = front + 1\n",
    "            # 更新窗口内元素\n",
    "            if temp in needs:\n",
    "                windows[temp] = windows.get(temp, 0) + 1\n",
    "                if windows[temp] == needs[temp]:\n",
    "                    valid = valid + 1\n",
    "            # 压缩窗口\n",
    "            while valid == len(needs):\n",
    "                if front - rear <= minLen:\n",
    "                    minLen = front - rear\n",
    "                    res = s[rear:front]\n",
    "                # 临时保存当前位置元素\n",
    "                temp = s[rear]\n",
    "                # 压缩窗口\n",
    "                rear = rear + 1\n",
    "                # 更新窗口内元素\n",
    "                if temp in needs:\n",
    "                    if windows[temp] == needs[temp]:\n",
    "                        valid = valid - 1\n",
    "                    windows[temp] = windows[temp] - 1\n",
    "        \n",
    "        return res\n",
    "\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minWindow(self, s: str, t: str) -> str:\n",
    "        # 假设s[left...right]中包含t的所有字符串\n",
    "        # 处理s[right] -> left向右移 -> 检查是否包含t的所有字符\n",
    "        res = \"\"\n",
    "        # 计算t的字符出现频次\n",
    "        char2cnt = {}\n",
    "        for i in range(len(t)):\n",
    "            char2cnt[t[i]] = char2cnt.get(t[i], 0) + 1\n",
    "        \n",
    "        # right开始右移\n",
    "        left = 0\n",
    "        for right in range(len(s)):\n",
    "            if s[right] in char2cnt:\n",
    "                char2cnt[s[right]] -= 1\n",
    "            \n",
    "            # left < right 且 left的移出不会使对应的cnt > 0\n",
    "            while left < right and (s[left] not in char2cnt or char2cnt[s[left]] < 0):\n",
    "                if s[left] in char2cnt:\n",
    "                    char2cnt[s[left]] += 1\n",
    "                left += 1\n",
    "            \n",
    "            # 检查是否所有的cnt都等于0\n",
    "            flag = True\n",
    "            for cnt in char2cnt.values():\n",
    "                flag = flag and cnt <= 0\n",
    "            if flag:\n",
    "                if res == \"\" or right - left + 1 < len(res):\n",
    "                    res = s[left: right+1]\n",
    "\n",
    "        return res"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
